栈的应用,力扣394.字符串解码力扣946.验证栈序列力扣429.N叉树的层序遍历力扣103.二叉树的锯齿形层序遍历
目录
力扣394.字符串解码
力扣946.验证栈序列
力扣429.N叉树的层序遍历
力扣103.二叉树的锯齿形层序遍历
力扣394.字符串解码
看见括号，由内而外，转向用栈解决。使用两个栈处理，一个用String,一个用Integer
遇到数字:提取数字放入到数字栈中
遇到'[':把后面的字符串提取出来，放入字符串栈中
遇到']':解析，然后放到字符串栈，栈顶的字符串后面，（因为，我们获取的是左括号里面的字符串，和数字，也就是我们知道是几个左括号里面的值，然后我们和前一个进行简单的拼接即可。
遇到单独的字符:提取出来这个字符，直接放在字符串栈顶的字符串后面。
class Solution { public static String decodeString(String s) { Stack<String>a=new Stack<>(); Stack<Integer>b=new Stack<>(); char[]ss=s.toCharArray(); //最终的存储结果的字符串 int i=0; while(i<ss.length){ StringBuffer ret=new StringBuffer(); int Mathret=0; //3[a2[ce]] acece ec //思路，存储[括号，直到遇上右括号，然后我们需要做什么呢？ 我们出来的顺序是ecec,或许可以考虑再存储一次？ // 左[上面的，如果是非空，我全给他排出来，再塞进去，再排出来?， //或者是否可以使用StringBuffer添加char,再来一个reverse是否更好呢。 if(ss[i]>='0'&&ss[i]<='9') { while (ss[i] >= '0' && ss[i] <= '9') { Mathret = Mathret * 10 + (ss[i] - '0'); i++; } b.add(Mathret); } else if(ss[i]=='['){ i++; while (i<ss.length&&ss[i] >= 'a' && ss[i] <= 'z') { ret.append(ss[i]); i++; } a.add(ret.toString()); } else if(ss[i]==']'){ String tem=a.pop(); StringBuffer p=new StringBuffer(); int count=b.pop(); while(count>0){ p.append(tem); count--; } if(!a.isEmpty()){ StringBuffer pc=new StringBuffer(a.pop()); pc.append(p); a.add(pc.toString()); }else{ a.add(""); StringBuffer pc=new StringBuffer(a.pop()); pc.append(p); a.add(pc.toString()); } i++; }//此时单独遇到字符情况 else{ while (i<ss.length&&ss[i] >= 'a' && ss[i] <= 'z') { ret.append(ss[i]); i++; } if(!a.isEmpty()){ StringBuffer pc=new StringBuffer(a.pop()); pc.append(ret); a.add(pc.toString()); }else{ a.add(""); StringBuffer pc=new StringBuffer(a.pop()); pc.append(ret); a.add(pc.toString()); } } } return a.pop(); } }
力扣946.验证栈序列
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer>a=new Stack<>();
//j表示pop的指针，i表示push的指针
int j=0;
//首先这个题考虑过程中，先考虑肯定是是否两个字符串长度不同。
for(int i=0;i<popped.length;i++){
a.add(pushed[i]);
while(!a.isEmpty()&&j<pushed.length&&popped[j]==a.peek()){
a.pop();
j++;
}
}
return a.size()==0;
}
}力扣429.N叉树的层序遍历
这里我遇到一个问题，就是我的ret不断添加的过程中，发现把ret2添加进去之后,ret2被我改变，但是ret也改变，我问了半天，没结果，然后我去问gpt得到了这个原因
在你的代码中，`ret2` 是一个 `List<Integer>` 类型的局部变量，用于存储当前层的所有节点值。当你将 `ret2` 添加到 `ret` 中时，实际上是将 `ret2` 的引用添加到了 `ret` 列表中。这意味着 `ret` 列表中的元素仍然指向同一个 `ret2` 对象。
因此，如果你在后续的循环中继续修改 `ret2`，那么 `ret` 列表中的对应元素也会受到影响，因为它们引用的是同一个对象。
result.add(new ArrayList<>(levelValues)); // 创建一个新的列表对象
}return result;
}
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
Queue<Node>q=new LinkedList<>();
List<List<Integer>>ret=new ArrayList<>();
if(root==null)return ret;
q.add(root);
while(!q.isEmpty()){
int sz=q.size();
List<Integer> ret2 = new ArrayList<>();
while(sz!=0) {
Node head = q.poll();
//暂时存储节点
ret2.add(head.val);
for (int i = 0; i < head.children.size(); i++) {
if(head.children!=null){
q.add(head.children.get(i));
}
}
sz--;
}
ret.add(new ArrayList<>(ret2));
}
return ret;
}
}力扣103.二叉树的锯齿形层序遍历
这个就是判断适当时机给他来个逆转就好，不难
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>>ret=new ArrayList<>();
if(root==null)return ret;
int count=0;
Queue<TreeNode>q=new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
List<Integer> ret2 = new ArrayList<>();
int sz=q.size();
while(sz!=0){
TreeNode t=q.poll();
ret2.add(t.val);
//注意我们思考一下，怎么出来才正确
if(t.left!=null)q.add(t.left);
if(t.right!=null)q.add(t.right);
sz--;
}
if(count%2==1){
List<Integer> ret3 = new ArrayList<>();
for(int i=ret2.size()-1;i>=0;i--){
ret3.add(ret2.get(i));
}
ret.add(new ArrayList<>(ret3));
}else{
ret.add(new ArrayList<>(ret2));}
count++;
}
return ret;
}
}