想不清楚的画图

stack 有几个用处

一个是reverse

445. Add Two Numbers II

不让reverse原来的链表那只好把所有ListNode放到stack然后 pop 考察链表 + 数字相加怎么从后往前构建链表 ~~ 移动tail指针

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack<Integer>();
        Stack<Integer> s2 = new Stack<Integer>();
        //put the listNode into the stack and then retrieve in reverse order 
        while(l1 != null){
            s1.push(l1.val);
            l1 = l1.next;
        }
        while(l2 != null){
            s2.push(l2.val);
            l2 = l2.next;
        }
        ListNode tail = null;
        int carry = 0;
        int sum = 0;
        while(!s1.isEmpty() || !s2.isEmpty()){
            int val1 = s1.isEmpty()? 0: s1.pop();
            int val2 = s2.isEmpty()? 0: s2.pop();
            sum = val1 + val2 + carry;
            ListNode node = new ListNode(sum % 10);
            node.next = tail;
            tail = node;
            carry = sum /10;
            sum = 0;
        }
        //多余的进位
        if(carry != 0){
            ListNode head = new ListNode(carry);
            head.next = tail;
            tail = head;
        }
        return tail;
    }
}

103. Binary Tree Zigzag Level Order Traversal

按照奇数偶数层分情况用stack作为翻转

还有一个是计算表达式

嗯电面的时候遇到原题一时想不到很简洁的做法用一个Stack 用正负区分直接计算保留结果遇到左括号保留原来的结果然后清0 继续计算遇到右括号弹出stack里面的元素计算非常简洁！！根本不用两个Stack倒来倒去

/** A simple version to solve this problem but may not be extended to include other operations **/
public class Solution {
    //compute the final result in the process 
    public int calculate(String s) {
        s.trim();
        char[] arr = s.toCharArray();
        int res = 0;
        int sign = 1;
        int len = arr.length;
        Stack<Integer> stack = new Stack<Integer>();
        for(int i = 0;i < arr.length;i++){
            char cur = arr[i];
            if(Character.isDigit(cur)){
                int sum = cur - '0';
                //一旦有index
                while(i+1 < len && Character.isDigit(arr[i+1])){
                    sum = sum * 10 + arr[i+1] - '0';
                    i++;
                }
                res += sum * sign;
            }
            else if(cur == '('){
                stack.push(res);
                stack.push(sign);
                //clear to 0 to start the calculation inside "("
                res = 0;
                sign = 1;
            }
            else if(cur == ')'){
                sign = stack.pop();
                res = res*sign;
                res += stack.pop();
            }
            else if(cur == '+'){
                sign = 1;
            }
            else {
                sign = -1;
            }
        }
        return res;
    }
}

做法和上一题一样变量+清零用一个Stack 一个当前value代表当前数字一个当前String表示一对括号中间的String 同时我们用一个stack存取之前已经形成的等下一次衔接的时候直接取出这样的思路写出来的代码很简洁！

public class Solution {
    public String decodeString(String s) {
        if(s == null || s.length() == 0)return "";
        int n = s.length();
        char[] arr = s.toCharArray();
        Stack<StringBuilder> strStack = new Stack();
        Stack<Integer> num = new Stack();
        StringBuilder bd = new StringBuilder();
        int val = 0;
        for(char cur:s.toCharArray()){
            if(Character.isDigit(cur)){
                val = val * 10 + cur - '0';
            }
            else if(cur == '['){
                strStack.push(bd);
                num.push(val);
                val = 0;
                bd = new StringBuilder();
            }
            else if(cur == ']'){
                int times = num.pop();
                //现在的
                StringBuilder tmp = bd;
                //之前的
                bd = strStack.pop();
                for(int i = 0;i < times;i++){
                    bd.append(tmp);
                }
            }
            else{
                bd.append(cur);
            }
        }
        return bd.toString();
    }
}

总结一下pattern 单独用一个变量表示当前的数字一个sign 表示符号

public class Solution {

    public NestedInteger deserialize(String s) {
        Stack<NestedInteger> stack = new Stack<NestedInteger>();
        NestedInteger result = new NestedInteger();
        if(s == null || s.length() == 0){
            return  result;
        }
        //we cannot skip this corner case because we first need to seperate the string according 
        if(s.charAt(0)!='['){
            result.setInteger(Integer.parseInt(s));
            return result;
        }
        int len = s.length();
        //the several digit number 
        int num = 0;
        int sign = 1;
        for(int i = 0;i < len;i++){
            char cur = s.charAt(i);
            if(cur == '-'){
                sign = -1;
            }
            else if(Character.isDigit(cur)){
                num = cur - '0';
                while((i+1)<len && Character.isDigit(s.charAt(i+1))){
                    num = num * 10 + s.charAt(i+1) - '0';
                    i++;
                }
                stack.peek().add(new NestedInteger(sign * num));
                sign = 1;
            }
            else if(cur == '['){ 
                NestedInteger tmp = new NestedInteger();
                stack.push(tmp);
            }
            else if(cur == ']'){
                 if(stack.size() > 1){
                     NestedInteger tmp = stack.peek();
                     stack.pop();
                     stack.peek().add(tmp);
                 }
             }
        }
        return stack.peek();
    }
}

150. Evaluate Reverse Polish Notation

比较简单的Stack的应用

public class Solution {
    //when encounter operation,pop two element from stack and compute and push
    //back the result
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack();
        String operation = "+-/*";
        for(String str : tokens){
            if(operation.contains(str)){
                int i1 = stack.pop();
                int i2 = stack.pop();
                if(str.equals("+")){
                    stack.push(i1 + i2);
                }
                else if(str.equals("-")){
                    stack.push(i2 - i1);
                }
                else if(str.equals("*")){
                    stack.push(i1 * i2);
                }
                else{
                    stack.push(i2 / i1);
                }
            }
            else{
                stack.push(Integer.parseInt(str));
            }
        }
        return stack.pop();
    }
}

iii. 还有一个作用是Container保存器暂时容器待会取出

84. Largest Rectangle in Histogram

对于每一个圆柱进行考虑就是考虑以每个圆柱高度作为宽度的矩阵最大是多少然后最终的结果从这些计算的结果里面取

怎么计算：对于每一个高度所能包含的只能是比自己高的如果遇到比自己矮的则不能继续延伸所以我们这里可以用一个Stack取存取在index i前面的圆柱的index 每次加入的时候如果比最高的高度高直接入stack 并且加上按照原来高度新增的

如果比最高的小弹出一些元素直到比当前元素高记录长度（index差值) 计算相应面积检验Stack是否为空如果是空则长度直接就是当前index 最终再检查一次是不是空处理所有剩余元素

单调stack
左边和右边第一个比它小的元素下标向左边看如果高度比当前的大则可以计算面积并且弹出

维持一个递增的stack

 public class Solution {
    /**
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    public int largestRectangleArea(int[] height) {
        // write your code here
        Stack<Integer> stack = new Stack();
        int n = height.length;
        int maxArea = 0;
        int i = 0;
        while(i <= n){
         //边缘
            int curh = (i == n)? 0 : height[i];
            if(stack.isEmpty() || curh >= height[stack.peek()]){
                stack.push(i++);
            }
            else{
                int h = height[stack.pop()];
                int w = (stack.isEmpty())? i:(i - stack.peek() - 1);
                maxArea = Math.max(maxArea,h * w);
            }
        }
        return maxArea;
    }
}

use the thought in No.84 , take every row as the base of the histogram compute the height of each spot. But we don't need to compute every spot over again, we can use the result of the former row. (Dynamic Programming) First we check whether the current element is 0, if it is zero we set the height to 0, if it is not we set it to be h[ i -1] + 1.

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length == 0||matrix[0].length == 0)return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int maxArea = 0;
        int[] height = new int[n];
        for(int i = 0;i < m;i++){
            //compute the height based on the result of last row!
            for(int j = 0;j < n;j++){
                height[j] = (matrix[i][j] == '1')? height[j] + 1 : 0;
            }
            maxArea = Math.max(maxArea,largestRectangleArea(height));
        }
        return maxArea;
    }
    public int largestRectangleArea(int[] height) {
        // write your code here
        Stack<Integer> stack = new Stack();
        int n = height.length;
        int maxArea = 0;
        int i = 0;
        while(i < n){
            if(stack.isEmpty() || height[i] >= height[stack.peek()]){
                stack.push(i++);
            }
            else{
                int h = height[stack.pop()];
                int w = (stack.isEmpty())? i:(i - stack.peek() - 1);
                maxArea = Math.max(maxArea,h * w);
            }
        }
        //if there are any left over element pay attention to the actual 
        //length!! 
        while(!stack.isEmpty()){
            int k = stack.pop();
            int len = (stack.isEmpty())? n : (n - stack.peek() - 1);
            maxArea = Math.max(maxArea,len * height[k]);
        }
        return maxArea;
    }
}

316. Remove Duplicate Letters

借用Stack完成比较因为我们要得到的是lexicographical最优所以我们先用stack存取结果字母然后做到每一步每一位取最小的每次将当前元素和栈顶元素比较如果栈顶的大而且还有剩余的我们可以先弹出压入当前较小的那个元素。最后形成结果的时候要遍历Stack这个有点tricky 因为不同的环境下遍历stack得到的结果可能是反的

   public String removeDuplicateLetters(String s) {
        Stack<Character> stack = new Stack<Character>();
        char[] arr = s.toCharArray();
        //use an array of 26 to load the number of each character
        int[] count = new int[26];
        boolean[] visited = new boolean[26];
        for(char c : arr){
            count[c - 'a']++;
        }
        //Iterate,push,pop from the array 
        for(char c : arr) {
             count[c-'a']--;
             if(visited[c-'a']) continue;
             while(!stack.isEmpty() && stack.peek() > c && count[stack.peek()-'a'] > 0) {
                 visited[stack.peek()-'a'] = false;
                 stack.pop();
             }
             stack.push(c);
             visited[c -'a'] = true;
        }
        StringBuilder bd = new StringBuilder();
        for(char i : stack){
            bd.append(i);
        }
        return bd.toString();
    }
}

Two Stack

155. Min Stack

use one more stack for storage of min, if smaller than min's peek() push to the min stack pay attention to the pop( ) : need to judge whether the poped element is the min of the set if it is also need to pop the minStack

class MinStack {
    // stack: store the stack numbers
    private Stack<Integer> stack = new Stack<Integer>();
    // minStack: store the current min values
    private Stack<Integer> minStack = new Stack<Integer>();

    public void push(int x) {
        // store current min value into minStack
        if (minStack.isEmpty() || x <= minStack.peek())
            minStack.push(x);
        stack.push(x);
    }

    public void pop() {
        // use equals to compare the value of two object, if equal, pop both of them
        if (stack.peek().equals(minStack.peek()))
            minStack.pop();
        stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

331. Verify Preorder Serialization of a Binary Tree

用stack的很难想要熟悉Pre Order 主要是观察什么时候出现“#”判断是在左子树还是右子树每次完成一个部分填补”#“

“case 1: you see a number c, means you begin to expand a new tree rooted with c, you push it to stack

case 2.1: you see a #, while top of stack is a number, you know this # is a left null child, put it there as a mark for next coming node k to know it is being the right child.

case 2.2: you see a #, while top of stack is #, you know you meet this # as right null child, you now cancel the sub tree (rooted as t, for example) with these two-# children. But wait, after the cancellation, you continue to check top of stack is whether # or a number:

---- if a number, say u, you know you just cancelled a node t which is left child of u. You need to leave a # mark to the top of stack. So that the next node know it is a right child.

---- if a #, you know you just cancelled a tree whose root, t, is the right child of u. So you continue to cancel sub tree of u, and the process goes on and on.”

public class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder == null) {
            return false;
        }
        Stack<String> stack = new Stack<>();
        String[] arr = preorder.split(",");
        for(int i = 0;i < arr.length;i++){
            if(!arr[i].equals("#")){
                stack.push(arr[i]);
            }
            else{
                //why two times because when we encounter the second "#" we know that we finished one part 
                //so we pop off the "triangle" area 
                while(!stack.isEmpty() && stack.peek().equals("#")){
                    stack.pop();
                    if(stack.isEmpty()){
                        return false;
                    }
                    stack.pop();
                }
                //and then push the "#" because we want to mark the upper TreeNode left part to be visited also
                //and continue the process!
                stack.push(arr[i]);
            }
        }
        //if we are finished since we always push an additional "#" when we finish thus the final result should
        //contain one and only node in the stack 
        return stack.size() == 1 && stack.peek().equals("#");. means current folder, .. means parent folde

去除Element

when encounter something delete something

71. Simplify Path

了解一下unix里面的path是怎么写的注意Iterate Stack的顺序(总感觉Stack别这么做直接pop然后reverse)

Stack

想不清楚的画图

stack 有几个用处

一个是reverse

445. Add Two Numbers II

不让reverse原来的链表那只好把所有ListNode放到stack然后 pop 考察链表 + 数字相加怎么从后往前构建链表 ~~ 移动tail指针

103. Binary Tree Zigzag Level Order Traversal

按照奇数偶数层分情况用stack作为翻转

还有一个是计算表达式

224. Basic Calculator

嗯电面的时候遇到原题一时想不到很简洁的做法用一个Stack 用正负区分直接计算保留结果遇到左括号保留原来的结果然后清0 继续计算遇到右括号弹出stack里面的元素计算非常简洁！！根本不用两个Stack倒来倒去

394. Decode String

做法和上一题一样变量+清零用一个Stack 一个当前value代表当前数字一个当前String表示一对括号中间的String 同时我们用一个stack存取之前已经形成的等下一次衔接的时候直接取出这样的思路写出来的代码很简洁！

385. Mini Parser

总结一下pattern 单独用一个变量表示当前的数字一个sign 表示符号

150. Evaluate Reverse Polish Notation

iii. 还有一个作用是Container保存器暂时容器待会取出

84. Largest Rectangle in Histogram

85. Maximal Rectangle

316. Remove Duplicate Letters

Two Stack

155. Min Stack

331. Verify Preorder Serialization of a Binary Tree

用stack的很难想要熟悉Pre Order 主要是观察什么时候出现“#”判断是在左子树还是右子树每次完成一个部分填补”#“

去除Element

71. Simplify Path

results matching ""

No results matching ""

想不清楚的画图

stack 有几个用处

一个是reverse

不让reverse原来的链表 那只好把所有ListNode放到stack然后 pop 考察链表 + 数字相加 怎么从后往前构建链表 ~~ 移动tail指针

按照奇数偶数层分情况 用stack作为翻转

还有一个是计算表达式

嗯电面的时候遇到原题 一时想不到很简洁的做法 用一个Stack 用正负区分 直接计算 保留结果 遇到左括号 保留原来的结果 然后清0 继续计算 遇到右括号 弹出stack里面的元素计算 非常简洁！！ 根本不用两个Stack倒来倒去

做法和上一题 一样 变量+清零 用一个Stack 一个当前value代表当前数字 一个当前String表示一对括号中间的String 同时我们用一个stack存取之前已经形成的 等下一次衔接的时候直接取出 这样的思路写出来的代码很简洁！

总结一下pattern 单独用一个变量表示当前的数字 一个sign 表示符号

iii. 还有一个作用是Container保存器 暂时容器 待会取出

Two Stack

Tree Related Traversal

用stack的很难想 要熟悉Pre Order 主要是观察什么时候出现“#”判断是在左子树还是右子树 每次完成一个部分 填补”#“

去除Element

results matching ""

No results matching ""

不让reverse原来的链表那只好把所有ListNode放到stack然后 pop 考察链表 + 数字相加怎么从后往前构建链表 ~~ 移动tail指针

按照奇数偶数层分情况用stack作为翻转

嗯电面的时候遇到原题一时想不到很简洁的做法用一个Stack 用正负区分直接计算保留结果遇到左括号保留原来的结果然后清0 继续计算遇到右括号弹出stack里面的元素计算非常简洁！！根本不用两个Stack倒来倒去

做法和上一题一样变量+清零用一个Stack 一个当前value代表当前数字一个当前String表示一对括号中间的String 同时我们用一个stack存取之前已经形成的等下一次衔接的时候直接取出这样的思路写出来的代码很简洁！

总结一下pattern 单独用一个变量表示当前的数字一个sign 表示符号

iii. 还有一个作用是Container保存器暂时容器待会取出

用stack的很难想要熟悉Pre Order 主要是观察什么时候出现“#”判断是在左子树还是右子树每次完成一个部分填补”#“