Review

  • 155 Min Stack
  • 42 Trapping Rain Water
  • 150 Evaluate Reverse Polish Notation
  • 173 Binary Search Tree Iterator
  • 85 Maximal Rectangle
  • 232 Implement Queue using Stacks
  • 84 Largest Rectangle in Histogram
  • 71 Simplify Path
  • 94 Binary Tree Inorder Traversal
  • 341 Flatten Nested List Iterator
  • 225 Binary Tree Postorder Traversal
  • 394 Decode String
  • 255 Verify Preorder Sequence in Binary Search Tree
  • 439 Ternary Expression Parser
  • 496 Next Greater Element I
  • 503 Next Greater Element II
  • 316 Remove Duplicate Letters
  • 227 Basic Calculator II
  • 224 Basic Calculator
  • 394 Decode String
  • 385 Mini Parser
  • 636 Exclusive Time of Functions
  • 331 Verify Preorder Serialization of a Binary Tree
  • 456 132 Pattern

155 Min Stack

思路： 两个栈的很容易写出来，但是要求一个栈来实现呢？

  • 一个栈存gap，一个数字存最小值,用long
  • 一个栈，一个数字存最小值，当遇到最小值时，存两次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
public class MinStack {
     Stack<Long>stk=null;
    long minVal;
    public MinStack() {
        stk=new Stack<>();
        minVal=Long.MAX_VALUE;
    }
    public void push(int x) {
        if(stk.isEmpty()){
            stk.push(0l);
            minVal=(long)x;
        }else{
            stk.push(x-minVal);
            minVal=Math.min(minVal,x);
        }
    }
    public void pop() {
        long val = stk.pop();
        if(val<0)//pay attention to this 
            minVal=(-val+minVal);
    }
	//pay attention to this 
    public int top() {
        if(stk.peek()<0)
            return (int)minVal;
        else
            return (int)(minVal+stk.peek());
    }
    public int getMin() {
        return (int)minVal;
    }
}
//wrong answer if no equals in x<=minVal
public class MinStack {
    Stack<Integer>stk=null;
    private int minVal;
    /** initialize your data structure here. */
    public MinStack() {
        minVal=Integer.MAX_VALUE;
        stk=new Stack<>();
    }
    
    public void push(int x) {
        if(x<=minVal){
            stk.push(minVal);
            minVal=x;
        }
        stk.push(x);
    }
    
    public void pop() {
        if(stk.pop()==minVal){
            minVal=stk.pop();
        }
        
    }
    
    public int top() {
        return stk.peek();
    }
    
    public int getMin() {
        return minVal;
    }
}

42 Traping rain water

思路： 单调栈来实现

  • 单调栈，和84题非常像
  • 两指针
  • 左右两数组记录最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int trap(int[] height) {
        int n = height.length;
        Stack<Integer> stk=new Stack<>();
        int area=0;
        for(int i=0;i<n;++i){
            while(!stk.isEmpty() && height[stk.peek()]<height[i]){
                int h = height[stk.pop()];
                int h1=stk.isEmpty()?0:height[stk.peek()];
                int w = stk.isEmpty()?i:i-1-stk.peek();
                area+=Math.max((Math.min(h1,height[i])-h)*w,0);
            }
            stk.push(i);
        }
        return area;
    }

150 Evaluate Reverse Polish Notation

思路： 栈和递归来实现

  • 栈
  • 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public int evalRPN(String[] tokens) {
         Stack<String>stk=new Stack<>();
        for(String token:tokens){
            if(token.equals("+")||token.equals("-")||token.equals("*")||token.equals("/")){
                if(stk.size()<2)
                    break;
                int val1= Integer.parseInt(stk.pop());
                int val2 = Integer.parseInt(stk.pop());
                if(token.equals("+"))
                    stk.push(String.valueOf(val2+val1));
                else if(token.equals("-"))
                    stk.push(String.valueOf(val2-val1));
                else if(token.equals("*"))
                    stk.push(String.valueOf(val2*val1));
                else
                    stk.push(String.valueOf(val2/val1));
            }else
                stk.push(token);
        }
        if(!stk.isEmpty())
            return Integer.parseInt(stk.peek());
        return 0;
    }
    
    
    //很奇怪，如果用li， start ，end会跪。
    public int eval(List<String>li){
        int n=li.size();
        String str=li.get(n-1);
        li.remove(n-1);
        if(str.equals("+")||str.equals("-")||str.equals("/")||str.equals("*")){
            int r1=eval(li);
            int r2=eval(li);
            if(str.equals("+"))
                return r1+r2;
            else if(str.equals("-"))
                return r2-r1;
            else if(str.equals("*"))
                return r2*r1;
            else
                return r2/r1;
        }
        return Integer.valueOf(str);
    }
    public int evalRPN(String []tokens){
        int n=tokens.length;
        List<String>li=new ArrayList<>(Arrays.asList(tokens));
        return eval(li);
    }

173 Binary Search Tree Iterator

思路： 其实就是stack的中序遍历，当然你可以先走一遍中序遍历，然后把所有的值都存到list里，但是这样的话非常耗space，常见的优化时lazy load

  • 中序遍历走一遍，存下所有的值
  • lazy load，必要的时候才继续载入值,记住 中序遍历是pop的，后序遍历是peek的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class BSTIterator {
   public Stack<TreeNode> stk=null;
    TreeNode cur=null;
    public BSTIterator(TreeNode root) {
        cur=root;
        stk=new Stack<>();
    }
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stk.isEmpty()||cur!=null;
    }
    /** @return the next smallest number */
    public int next() {
       int val=0;
        while(cur!=null){
            stk.push(cur);
            cur=cur.left;
        }
        cur=stk.pop();
        val=cur.val;
        cur=cur.right;
        return val;
    }
}

84 Largest Rectangle in Histogram && 85 Maximal Rectangle 以及trapping rain water 是姊妹题

思路：单调栈和动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//84 largest rectangle in histgram
public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Stack<Integer>stk=new Stack<>();
        int maxArea=0;
        for(int i=0;i<=n;++i){
            int height=i<n?heights[i]:0;
            while(!stk.isEmpty() && heights[stk.peek()]>height){
                int h = heights[stk.pop()];
                int w = stk.isEmpty()?i:i-stk.peek()-1;//i is not in the area
                maxArea=Math.max(maxArea,h*w);
            }
            stk.push(i);
        }
        return maxArea;
    }
    //85 maximal rectangle
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length==0||matrix[0].length==0)
            return 0;
        int m = matrix.length,n=matrix[0].length;
        int []dp=new int[n];
        for(int i=0;i<n;++i){
            dp[i]=matrix[0][i]=='1'?1:0;
        }
        int maxArea=largestRectangleArea(dp);
        for(int i=1;i<m;++i){
            for(int j=0;j<n;++j){
                dp[j]=matrix[i][j]=='0'?0:dp[j]+1;
            }
            maxArea=Math.max(maxArea,largestRectangleArea(dp));
        }
        return maxArea;
    }

232 Implement Queue using Stacks

思路： 两stack，两stack 是不平等的关系， stack2是优先级比较高的。

  • two stack, push is O(1), others are O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class MyQueue {
    //two stack, uneven
    public Stack<Integer> stk=null;//primary stack;
    public Stack<Integer>stk1=null;
    /** Initialize your data structure here. */
    public MyQueue() {
        stk=new Stack<>();
        stk1=new Stack<>();
    }
    /** Push element x to the back of queue. */
    public void push(int x) {
        stk.push(x);
    }
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(!stk1.isEmpty())
            return stk1.pop();
        while(!stk.isEmpty())
            stk1.push(stk.pop());
        return stk1.pop();
    }
    /** Get the front element. */
    public int peek() {
        if(!stk1.isEmpty())
            return stk1.peek();
        while(!stk.isEmpty())
            stk1.push(stk.pop());
        return stk1.peek();
    }
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stk.isEmpty() && stk1.isEmpty();
    }
}

225. Implement Stack using Queues

思路： 两queue，相等的地位，每次都是剩下一个元素，剩下的push到另一外一个queue

  • 两个queue， push是o(1)， 其他是o(n)
  • 一个queue，push是o(n)，其他是o(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
public class MyStackOneQueue {
    /** Initialize your data structure here. */
    private Queue<Integer> q=null;
    public MyStackOneQueue() {
        q=new LinkedList<>();
    }
    /** Push element x onto stack. */
    public void push(int x) {
        q.offer(x);
        for(int i=0;i<q.size()-1;++i){
            q.offer(q.poll());
        }
    }
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return q.poll();
    }
    /** Get the top element. */
    public int top() {
        return q.peek();
    }
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return q.isEmpty();
    }
}
public class MyStack {
      //two queue even
    Queue<Integer> q=null;
    Queue<Integer>q1=null;
    /** Initialize your data structure here. */
    public MyStack() {
        q=new LinkedList<>();
        q1=new LinkedList<>();
    }
    /** Push element x onto stack. */
    public void push(int x) {
        q.offer(x);
    }
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        int val=0;
        if(!q.isEmpty()){
            while(q.size()>1){
                q1.offer(q.poll());
            }
            val=q.poll();
        }else{
            while(q1.size()>1){
                q.offer(q1.poll());
            }
            val=q1.poll();
        }
        return val;
    }
    /** Get the top element. */
    public int top() {
        int val=0;
        if(!q.isEmpty()){
            while(q.size()>1){
                q1.offer(q.poll());
            }
            val=q.poll();
            q1.offer(val);
        }else{
            while(q1.size()>1){
                q.offer(q1.poll());
            }
            val=q1.poll();
            q.offer(val);
        }
        return val;
    }
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return q.isEmpty() && q1.isEmpty();
    }
}

71. Simplify Path

思路： 切割， !stk.isEmpty && str==”..” 出栈, str!=’.’ && str!=’..’ str!=”” 就加到stack里,最后别忘了加上 “/”。

1
2
3
4
5
6
7
8
9
10
11
12
public String simplifyPath(String path) {
        String []paths = path.split("/");
        Stack<String>stk=new Stack<>();
        for(String str:paths){
            if(!stk.isEmpty() && str.equals("..")){
                stk.pop();
            }else if(!str.equals(".") && str.length()!=0 && !str.equals(".."))
                stk.push(str);
        }
        String res = String.join("/",stk);
        return "/"+res;
    }

94 binary tree inorder traversal

思路： 掌握三种，递归，stack，莫里斯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer>res = new ArrayList<>();
        TreeNode cur = root;
        Stack<TreeNode>stk=new Stack<TreeNode>();
        while(cur!=null||!stk.isEmpty()){
            while(cur!=null){
                stk.push(cur);
                cur=cur.left;
            }
            cur=stk.pop();
            res.add(cur.val);
            cur=cur.right;
        }
        return res;
    }

341 flatten nested list iterator

思路： 可以一次性遍历完，然后再遍历，但是这样的话空间复杂度太高

  • 一次性遍历完
  • lazy load，需要的时候才遍历，用到栈, queue就不行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class NestedIterator implements Iterator<Integer> {
    private Stack<NestedInteger> stk=null;
    public NestedIterator(List<NestedInteger> nestedList) {
        stk=new Stack<>();
        int n=nestedList.size();
        for(int i=n-1;i>=0;--i){
            if(!nestedList.get(i).isInteger()){
                if(nestedList.get(i).getList().isEmpty())
                    continue;
            }
            stk.push(nestedList.get(i));
        }
    }
    @Override
    public Integer next() {
        return stk.pop().getInteger();
    }
    @Override
    public boolean hasNext() {
        while(!stk.isEmpty() && !stk.peek().isInteger()){
            NestedInteger top=stk.pop();
            if(top.isInteger()){
                stk.push(top);
                System.out.println("a");
                break;
            }else{
                List<NestedInteger>nestedList=top.getList();
                int n=nestedList.size();
                for(int i=n-1;i>=0;--i){
                    if(!nestedList.get(i).isInteger()){
                        if(nestedList.get(i).getList().isEmpty())
                            continue;
                    }
                    stk.push(nestedList.get(i));
                }
            }
        }
        return !stk.isEmpty();
    }
}

145 Binary Tree Postorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
TreeNode pre =null;
   public List<Integer> postorderTraversal(TreeNode root) {
       List<Integer>res=new ArrayList<>();
       if(root==null)
           return res;
       Stack<TreeNode>stk=new Stack<>();
       TreeNode curr = root;
       while (!stk.isEmpty() || curr != null) {
           while(curr!=null){
               stk.push(curr);
               curr=curr.left;
           }
           curr=stk.peek();
           if(curr.right!=null && curr.right!=pre){//没有被访问
               curr=curr.right;
           }else{
               res.add(curr.val);
               pre=curr;
               stk.pop();
               curr=null;
           }
       }
       return res;
   }

439. Ternary Expression Parser

思路： 反着入栈,递归容易爆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String parseTernary(String expression) {
        Stack<Character>stk=new Stack<>();
        char []ss=expression.toCharArray();
        //when finding ?, it is your chance
        int n = ss.length,i=n-1;
        while(i>=0){
            if(ss[i]!='?' && ss[i]!=':')
                stk.push(ss[i]);
            else if(ss[i]=='?'){
                char c1= stk.pop();
                char c2=stk.pop();
                stk.push(ss[i-1]=='T'?c1:c2);
                i-=2;
                continue;
            }
            i--;
        }
        return String.valueOf(stk.peek());
    }

496 next greater element I

思路： stack专门找第一个比它大的元素。递减，然后找到一个大的，那么就出栈，这些出栈的元素的最近大的元素都是它。在这里我们用hashmap建立联系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] nextGreaterElement(int[] findNums, int[] nums) {
         int n = findNums.length,m=nums.length;
        int []res=new int[n];
        //先一个map建起来
        Map<Integer,Integer>map=new HashMap<>();
        Stack<Integer>stk=new Stack<>();
        for(int i=0;i<m;++i){
            while(!stk.isEmpty() && stk.peek()<nums[i]){
                map.put(stk.pop(),nums[i]);
            }
            stk.push(nums[i]);
        }
        Arrays.fill(res,-1);
        for(int i=0;i<n;++i){
            if(map.containsKey(findNums[i]))
                res[i]=map.get(findNums[i]);
        }
        return res;
    }

503. Next Greater Element II

思路： 和上题差不多，环状的话走两遍，2*n，然后用mod，这个不需要hashmap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] nextGreaterElements(int[] nums) {
        int n=nums.length;
        int []res=new int[n];
        Arrays.fill(res,-1);
        Stack<Integer>stk=new Stack<>();
        for(int i=0;i<2*n;++i){
            while(!stk.isEmpty() && nums[i%n]>nums[stk.peek()]){
                res[stk.pop()]=nums[i%n];
            }
            //if(i<n)
            stk.push(i%n);
        }
        return res;
    }

316.Remove Duplicate Letters

思路： 先统计26个char的分布，同时记住哪些被访问过，用stack装。只有当后面还有这个字符，且这个字符大于或等于当前字符才可以替换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public String removeDuplicateLetters(String s) {
        int []cnt=new int[26];
        char []ss=s.toCharArray();
        for(char c:ss)
            cnt[c-'a']++;
        Stack<Character>stk=new Stack<>();
        boolean []vis = new boolean[26];
        for(char c:ss){
            --cnt[c-'a'];
            if(vis[c-'a'])
                continue;
            while(!stk.isEmpty() && cnt[stk.peek()-'a']>0 && stk.peek()>=c){
                char cc = stk.pop();
                vis[cc-'a']=false;
            }
            stk.push(c);
            vis[c-'a']=true;
        }
        StringBuilder sb = new StringBuilder();
        while(!stk.isEmpty()){
            sb.append(stk.pop());
        }
        sb.reverse();
        return sb.toString();
    }

227.Basic Calculator II

思路： 笨一点可以用stk装，以后可以优化，令我非常惊奇的是如何做到： 计算完当前的数字，此时符号是它前面的“+ - * ／”

  • stk
  • without stk
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
public int calculate(String s) {
         int n=s.length();
        char []ss=s.toCharArray();
        Stack<Integer>stk=new Stack<>();
        int num =0;
        char sign ='+';
        int ans=0,prev=0;
        for(int i=0;i<n;++i){
            if(Character.isDigit(ss[i])){
                num=10*num+(ss[i]-'0');
            }
            if((!Character.isDigit(ss[i]) && ss[i]!=' ')|| i==n-1 ){
                if(sign=='-'){
                    ans+=prev;
                    prev=-num;
                }
                else if(sign=='+'){
                    ans+=prev;
                    prev=num;
                }
                else if(sign=='*'){
                    prev=prev*num;
                }else if(sign=='/'){
                    prev=prev/num;
                }
                sign=ss[i];//放在后面真是很巧妙啊,就省得向我这样蛮干了。
                num=0;
            }
        }
        return ans+=prev;
        
        
        
    public int calculate(String s) {
	    int len;
	    if(s==null || (len = s.length())==0) return 0;
	    Stack<Integer> stack = new Stack<Integer>();
	    int num = 0;
	    char sign = '+';
	    for(int i=0;i<len;i++){
	        if(Character.isDigit(s.charAt(i))){
	            num = num*10+s.charAt(i)-'0';
	        }
	        if((!Character.isDigit(s.charAt(i)) &&' '!=s.charAt(i)) || i==len-1){
	            if(sign=='-'){
	                stack.push(-num);
	            }
	            if(sign=='+'){
	                stack.push(num);
	            }
	            if(sign=='*'){
	                stack.push(stack.pop()*num);
	            }
	            if(sign=='/'){
	                stack.push(stack.pop()/num);
	            }
	            sign = s.charAt(i);
	            num = 0;
	        }
	    }
	
	    int re = 0;
	    for(int i:stack){
	        re += i;
	    }
	    return re;
}

224. Basic Calculator

思路： 每遇到(，就把res入栈，符号入栈,遇到) 就弹出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public int calculate(String s) {
        int n = s.length();
        char []ss=s.toCharArray();
        Stack<Integer>stk=new Stack<>();
        int sign=1,res=0,num=0;
        for(int i=0;i<n;++i){
            if(i<n && Character.isDigit(ss[i])){
                num=10*num+(ss[i]-'0');
            }
            if((!Character.isDigit(ss[i]) && ss[i]!=' ')||i==n-1){
                if(ss[i]=='+'){
                    res+=sign*num;
                    sign=1;
                    num=0;
                }
                else if(ss[i]=='-'){
                    res+=sign*num;
                    sign=-1;
                    num=0;
                }else if(ss[i]=='('){
                    stk.push(res);
                    stk.push(sign);
                    sign=1;
                    res=0;
                    num=0;
                }else if(ss[i]==')'){
                    res+=num*sign;
                    res*=stk.pop();
                    res+=stk.pop();
                    sign=1;
                    num=0;
                }
            }
        }
        return res+=sign*num;
    }

385. Mini Parser

思路： 遇到做括号，就存到栈里，遇到右括号就先pop，然后再加上当前的.

  • recursive way
  • stk way
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public NestedInteger deserialize(String s) {
        if(s.isEmpty())
            return new NestedInteger();
        if(s.charAt(0)!='[')
            return new NestedInteger(Integer.parseInt(s));
        Stack<NestedInteger>stk=new Stack<>();
        NestedInteger res = new NestedInteger();
        int ind=1,n=s.length(),sign=1;
        char []ss=s.toCharArray();
        while(ind<n-1) {
            if(ss[ind]=='-'){
                ind++;
                sign=-1;
            }
            if(ind<n-1 && Character.isDigit(ss[ind])){
                int num =0;
                while(ind<n-1 && Character.isDigit(ss[ind])){
                    num=10*num+(ss[ind++]-'0');
                }
                res.add(new NestedInteger(sign*num));
                sign=1;
            }
            if(ind<n-1 && ss[ind]==','){
                ind++;
            }
            if(ind<n-1 && ss[ind]=='['){
                stk.add(res);
                res = new NestedInteger();
                ind++;
            }
            if(ind<n-1 && ss[ind]==']' && !stk.isEmpty()){
                NestedInteger tmp = stk.pop();
                tmp.add(res);
                res=tmp;
                ind++;
            }
        }
        return res;
    }

394. Decode String

思路： 两个stk，一个专门存数字，一个存字符串，遇到左括号就存到栈里，遇到右括号就从两个栈里弹出内容.

  • recursive way
  • stk way
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public String decodeString(String s) {
        int ind=0,n = s.length();
        char []ss = s.toCharArray();
        Stack<Integer>num=new Stack<>();
        Stack<String>stk=new Stack<>();
        StringBuilder sb = new StringBuilder();
        while(ind<n){
            if(Character.isDigit(ss[ind])){
                int number = 0;
                while(ind<n && Character.isDigit(ss[ind])){
                    number=10*number+(ss[ind++]-'0');
                }
                num.push(number);
            }
            if(ind<n && ss[ind]=='['){
                stk.push(sb.toString());
                sb.setLength(0);
                ind++;
            }else if(ind<n && ss[ind]==']'){
                StringBuilder tmp = new StringBuilder(stk.pop());
                int repeat = num.pop();
                while(repeat-- >0){
                    tmp.append(sb.toString());
                }
                sb=tmp;
                ind++;
            }else if(ind<n)
                sb.append(ss[ind++]);
        }
        return sb.toString();
    }

636. Exclusive Time of Functions

思路：遇到start就入栈，如栈的包括id，time，已被使用的时间,主要的难点是递归的话要叠加时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] exclusiveTime(int n, List<String> logs) {
        int []res =new int[n];
        Stack<int[]>stk=new Stack<>();//first index is id, second is start time,third is gap
        int cnt=0;
        for(String str:logs){
            String[]strs=str.split(":");
            if(strs[1].equals("start")){
                stk.push(new int[]{Integer.parseInt(strs[0]),Integer.parseInt(strs[2]),0});
            }else if(strs[1].equals("end")){
                int []top=stk.pop();
                int val = Integer.parseInt(strs[2]);
                res[top[0]]+=val-top[1]+1-top[2];
                cnt=val-top[1]+1;
                if(!stk.isEmpty())
                    stk.peek()[2]+=cnt;
            }
        }
        return res;
    }

331. Verify Preorder Serialization of a Binary Tree

思路：每遇到两个##就删除，并把之前的变成#。并且要能循环处理这种情况。当然也是可以用入度，出度来做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public boolean isValidSerialization(String preorder) {
        String[]args=preorder.split(",");
        int n =args.length;
        Stack<String>stk=new Stack<>();
        for(int i=0;i<=n;++i){
            if(i<n){
                if(args[i].equals("#") && !stk.isEmpty() && stk.peek().equals("#")){
                    stk.pop();
                    if(stk.isEmpty())
                        return false;
                    stk.pop();
                    stk.push("#");
                }
                else
                    stk.push(args[i]);
            }
            while(stk.size()>=3){
                    if(stk.peek().equals("#")){
                        String top = stk.pop();
                        if(stk.peek().equals("#")){
                            stk.pop();
                            stk.pop();
                            stk.push("#");
                        }else{
                            stk.push(top);
                            break;
                        }
                    }else
                        break;
                }
        }
        return stk.size()==1 && stk.peek().equals("#");
    }
    
    
   
 public boolean isValidSerializationSaveTime(String preorder){
        String []args = preorder.split(",");
        int diff=1;
        for(String c:args){
            if(--diff<0)
                return false;
            if(!c.equals("#"))//入度减1，出度加2，但是是#就不加
                diff+=2;
        }
        return diff==0;
    }

456 132 Pattern

思路：有点像 334. Increasing Triplet Subsequence。注意这种不能简单的用单调栈来解决，单调栈会把数改变。我们要的是小于当前数的最大数。

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean find132pattern(int[] nums) {
        Stack<Integer> stk=new Stack<>();
        int n=nums.length,s3=Integer.MIN_VALUE;
        for(int i=n-1;i>=0;--i){
            if(nums[i]<s3)
                return true;
            while(!stk.isEmpty() && stk.peek()<nums[i]){
                s3=stk.pop();
            }
            stk.push(nums[i]);
        }
        return false;
    }

Expectations

  • 本来还想修改着简历的，时间太晚了，控制不好工作量
  • 做过的题要及时复习

三番