栈的应用,力扣394.字符串解码力扣946.验证栈序列力扣429.N叉树的层序遍历力 ...

目次

力扣394.字符串解码
力扣946.验证栈序列
力扣429.N叉树的层序遍历
力扣103.二叉树的锯齿形层序遍历

---

力扣394.字符串解码

   瞥见括号，由内而外，转向用栈解决。使用两个栈处理，一个用String,一个用Integer
  遇到数字:提取数字放入到数字栈中
  遇到'[':把背面的字符串提取出来，放入字符串栈中
  遇到']':剖析，然后放到字符串栈，栈顶的字符串背面，（由于，我们获取的是左括号内里的字符串，和数字，也就是我们知道是几个左括号内里的值，然后我们和前一个进行简单的拼接即可。
  遇到单独的字符:提取出来这个字符，直接放在字符串栈顶的字符串背面。

1. class Solution {
2. public static String decodeString(String s) {
3.     Stack<String>a=new Stack<>();
4.     Stack<Integer>b=new Stack<>();
5.     char[]ss=s.toCharArray();
6.     //最终的存储结果的字符串
7.         int i=0;
8.         while(i<ss.length){
9.             StringBuffer ret=new StringBuffer();
10.             int Mathret=0;
11. //3[a2[ce]] acece        ec
12.         //思路，存储[括号，直到遇上右括号，然后我们需要做什么呢？ 我们出来的顺序是ecec,或许可以考虑再存储一次？
13.         // 左[上面的，如果是非空，我全给他排出来，再塞进去，再排出来?，
14.         //或者是否可以使用StringBuffer添加char,再来一个reverse是否更好呢。
15.             if(ss[i]>='0'&&ss[i]<='9') {
16.                 while (ss[i] >= '0' && ss[i] <= '9') {
17.                     Mathret = Mathret * 10 + (ss[i] - '0');
18.                     i++;
19.                 }
20.                 b.add(Mathret);
21.             }
22.    else  if(ss[i]=='['){
23.             i++;
24.                 while (i<ss.length&&ss[i] >= 'a' && ss[i] <= 'z') {
25.                     ret.append(ss[i]);
26.                     i++;
27.                 }
28.                 a.add(ret.toString());
29.         }
30.       else  if(ss[i]==']'){
31.           String tem=a.pop();
32.           StringBuffer p=new StringBuffer();
33.           int count=b.pop();
34.           while(count>0){
35.               p.append(tem);
36.               count--;
37.           }
38.           if(!a.isEmpty()){
39.               StringBuffer pc=new StringBuffer(a.pop());
40.               pc.append(p);
41.               a.add(pc.toString());
42.           }else{
43.               a.add("");
44.               StringBuffer pc=new StringBuffer(a.pop());
45.               pc.append(p);
46.               a.add(pc.toString());
48.           }
49.             i++;
50.         }//此时单独遇到字符情况
51.       else{
52.                 while (i<ss.length&&ss[i] >= 'a' && ss[i] <= 'z') {
53.                     ret.append(ss[i]);
54.                     i++;
55.                 }
56.                 if(!a.isEmpty()){
57.                     StringBuffer pc=new StringBuffer(a.pop());
58.                     pc.append(ret);
59.                     a.add(pc.toString());
60.                 }else{
61.                     a.add("");
62.                     StringBuffer pc=new StringBuffer(a.pop());
63.                     pc.append(ret);
64.                     a.add(pc.toString());
65.                 }
66.             }
68.     }
69.     return a.pop();
70. }
71. }

复制代码

  力扣946.验证栈序列

1. class Solution {
2.     public boolean validateStackSequences(int[] pushed, int[] popped) {
3.         Stack<Integer>a=new Stack<>();
4.         //j表示pop的指针，i表示push的指针
5.         int j=0;
6.         //首先这个题考虑过程中，先考虑肯定是是否两个字符串长度不同。
7.         for(int i=0;i<popped.length;i++){
8.             a.add(pushed[i]);
9.             while(!a.isEmpty()&&j<pushed.length&&popped[j]==a.peek()){
10.                 a.pop();
11.                 j++;
12.             }
13.         }
14.         return a.size()==0;
15.     }
16. }

复制代码

力扣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;
}

1. /*
2. // Definition for a Node.
3. class Node {
4.     public int val;
5.     public List<Node> children;
7.     public Node() {}
9.     public Node(int _val) {
10.         val = _val;
11.     }
13.     public Node(int _val, List<Node> _children) {
14.         val = _val;
15.         children = _children;
16.     }
17. };
18. */
20. class Solution {
21.         public  List<List<Integer>> levelOrder(Node root) {
22.         Queue<Node>q=new LinkedList<>();
23.         List<List<Integer>>ret=new ArrayList<>();
24.         if(root==null)return ret;
25.         q.add(root);
27.         while(!q.isEmpty()){
28.             int sz=q.size();
29.             List<Integer> ret2 = new ArrayList<>();
30.             while(sz!=0) {
31.                 Node  head = q.poll();
32.                 //暂时存储节点
33.                  ret2.add(head.val);
34.                     for (int i = 0; i < head.children.size(); i++) {
35.                         if(head.children!=null){
36.                         q.add(head.children.get(i));
37.               }   
38.            }
39.             sz--;
40.         }      
41.                 ret.add(new ArrayList<>(ret2));      
42.             }
44.         return ret;
45.     }
46. }

复制代码

力扣103.二叉树的锯齿形层序遍历

   这个就是判断恰当时机给他来个逆转就好，不难

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;
5. *     TreeNode left;
6. *     TreeNode right;
7. *     TreeNode() {}
8. *     TreeNode(int val) { this.val = val; }
9. *     TreeNode(int val, TreeNode left, TreeNode right) {
10. *         this.val = val;
11. *         this.left = left;
12. *         this.right = right;
13. *     }
14. * }
15. */
16. class Solution {
17.     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
18.         List<List<Integer>>ret=new ArrayList<>();
19.         if(root==null)return ret;
20.         int count=0;
21.         Queue<TreeNode>q=new LinkedList<>();
22.         q.add(root);
23.         while(!q.isEmpty()){
24.         List<Integer> ret2 = new ArrayList<>();
25.         int sz=q.size();
26.         while(sz!=0){
27.         TreeNode t=q.poll();
28.         ret2.add(t.val);
29.         //注意我们思考一下，怎么出来才正确
30.         if(t.left!=null)q.add(t.left);
31.         if(t.right!=null)q.add(t.right);
32.             sz--;
33.         }
35.         if(count%2==1){
36.                  List<Integer> ret3 = new ArrayList<>();
37.                  for(int i=ret2.size()-1;i>=0;i--){
38.                     ret3.add(ret2.get(i));
39.                  }
40.            ret.add(new ArrayList<>(ret3));
41.         }else{
42.         ret.add(new ArrayList<>(ret2));}
44.         count++;
45.         }
46.         return ret;
47.     }
48. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。