2016年11月26日星期六

Stack

1. Mini Parser
Given a nested list of integers represented as a string, implement a parser to deserialize it.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Note: You may assume that the string is well-formed:
  • String is non-empty.
  • String does not contain white spaces.
  • String contains only digits 0-9, [, - ,, ].
Example 1:
Given s = "324",

You should return a NestedInteger object which contains a single integer 324.
Example 2:
Given s = "[123,[456,[789]]]",

Return a NestedInteger object containing a nested list with 2 elements:

1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789.
对于后边儿的NestedInteger而言，它的parent还是需要的。因此用stack，在遇到'['的时候，push前边儿那个是list的NestedInteger。那个NestedInteger就是后边儿哪层的parent

 
 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
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class Solution {
    public NestedInteger deserialize(String s) {
        int num = 0, sign=1;
        Stack<NestedInteger> stack = new Stack<>();
        NestedInteger ni = null;
        if (s.charAt(0) != '[') // ERROR: special case
            return new NestedInteger(Integer.valueOf(s));
        for(int i =0;i<s.length(); i++){
            char c = s.charAt(i);
            if(c == '['){
                //here comes a new list
                if(ni!=null && !ni.isInteger())
                    stack.push(ni);
                ni = new NestedInteger();
                if(!stack.empty()){
                    stack.peek().add(ni);
                }
            }else if ( c == ']'){
                //complete
                if(Character.isDigit(s.charAt(i-1))){
                    ni.add(new NestedInteger(sign*num));
                    num = 0;
                    sign = 1;
                }
                if(!stack.empty())
                    ni = stack.pop();
            }else if( c == ','){
                if(Character.isDigit(s.charAt(i-1))){
                    ni.add(new NestedInteger(sign*num));
                    num = 0;
                    sign = 1;
                }
            }else if( c == '-'){
                sign = -1;
            }else{
                num=num*10+c-'0';
            }
        }
        return ni;
    }
}

2.Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
如果第i个位置，高度比前边儿的都高，那么前边儿的都没用了，第i+1个位置或者以后对0到i-1那些位置都没有作用了
维护一个单调递减的stack，里边儿放index，第边儿是h[stack.pop()] ， 上边儿是min(h[i],h[stack.peek()])，宽是i-stack.peek()

 如果和stack顶一样高，保留index大的那个（[5,2,1,2,1,5]例子里边儿两个2，如果保留第一个2，在算以最后那个1为底边的时候，left index is not correct）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int trap(int[] height) {
        int bottom = 0;
        Stack < Integer> stack = new Stack<>();
        int ret = 0, n = height.length;
        if(n == 0) return 0;
        for(int i =0; i < n; i++){
            while(!stack.empty() && height[i] > height[stack.peek()]){
                bottom = stack.pop();
                if(stack.size()!=0)
                    ret += 
                        (Math.min(height[i] ,height[stack.peek()]) - height[bottom])*(i-stack.peek()-1);
            }
            if(stack.empty() || height[i] < height[stack.peek()]){
                stack.push(i);
            }
            if(height[i] == height[stack.peek()]){stack.pop(); stack.push(i);}
        }
        return ret;
    }
}

 3. Maximal Rectangle
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 6.

 
 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
public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if(m == 0) return 0;
        int n = matrix[0].length;
        int[] heights = new int[n];
        int max = 0;
        for(int i = 0; i<m ;i++){
            for(int j = 0; j < n ; j++){
                if(matrix[i][j]=='1')
                    heights[j] += 1;
                else
                    heights[j] = 0;
            }
           max = Math.max(max, largestRectangleArea(heights)); 
        }
         return max;
    }
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack =new Stack<>();
        int n = heights.length;
        int max = 0;
        for(int i = 0; i < n;){
            if(stack.empty()||heights[i] > heights[stack.peek()])
                stack.push(i++);
            else{
                int h = heights[stack.pop()];
                max =Math.max(max, h*(stack.empty()? i : (i-stack.peek()-1)));
            }
        }
        int i = n;
        while(!stack.empty()){
            int h = heights[stack.pop()];
            max =Math.max(max, h*(stack.empty()? i : (i-stack.peek()-1)));           
        }
        return max;
    }
}
he DP solution proceeds row by row, starting from the first row. Let the maximal rectangle area at row i and column j be computed by [right(i,j) - left(i,j)]*height(i,j).
All the 3 variables left, right, and height can be determined by the information from previous row, and also information from the current row. So it can be regarded as a DP solution. The transition equations are:
left(i,j) = max(left(i-1,j), cur_left), cur_left can be determined from the current row
right(i,j) = min(right(i-1,j), cur_right), cur_right can be determined from the current row
height(i,j) = height(i-1,j) + 1, if matrix[i][j]=='1';
height(i,j) = 0, if matrix[i][j]=='0'
The code is as below. The loops can be combined for speed but I separate them for more clarity of the algorithm.
class Solution {public:
int maximalRectangle(vector<vector<char> > &matrix) {
    if(matrix.empty()) return 0;
    const int m = matrix.size();
    const int n = matrix[0].size();
    int left[n], right[n], height[n];
    fill_n(left,n,0); fill_n(right,n,n); fill_n(height,n,0);
    int maxA = 0;
    for(int i=0; i<m; i++) {
        int cur_left=0, cur_right=n; 
        for(int j=0; j<n; j++) { // compute height (can do this from either side)
            if(matrix[i][j]=='1') height[j]++; 
            else height[j]=0;
        }
        for(int j=0; j<n; j++) { // compute left (from left to right)
            if(matrix[i][j]=='1') left[j]=max(left[j],cur_left);
            else {left[j]=0; cur_left=j+1;}
        }
        // compute right (from right to left)
        for(int j=n-1; j>=0; j--) {
            if(matrix[i][j]=='1') right[j]=min(right[j],cur_right);
            else {right[j]=n; cur_right=j;}    
        }
        // compute the area of rectangle (can do this from either side)
        for(int j=0; j<n; j++)
            maxA = max(maxA,(right[j]-left[j])*height[j]);
    }
    return maxA;
}
};
If you think this algorithm is not easy to understand, you can try this example:
0 0 0 1 0 0 0 
0 0 1 1 1 0 0 
0 1 1 1 1 1 0
The vector "left" and "right" from row 0 to row 2 are as follows
row 0:
l: 0 0 0 3 0 0 0
r: 7 7 7 4 7 7 7
row 1:
l: 0 0 2 3 2 0 0
r: 7 7 5 4 5 7 7
row 2:
l: 0 1 2 3 2 1 0
r: 7 6 5 4 5 6 7
The vector "left" is computing the left boundary. Take (i,j)=(1,3) for example. On current row 1, the left boundary is at j=2. However, because matrix[1][3] is 1, you need to consider the left boundary on previous row as well, which is 3. So the real left boundary at (1,3) is 3.


4. Remove Duplicate Letters
Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example:
Given "bcabc"
Return "abc"
Given "cbacdcbc"
Return "acdb"
you need to know whether to keep current character:
1. if it's larger than previous one, keep it, i++
2. else, if previous one has more in later sequence, we remove previousThus we need a stack (LIFO), we want the stack to be increasing sequence as much as we can
we also need count # of characters in input.(map)
1. forgot duplicate later
Input:"cbacdcbc"
Output:"acdbc"
Expected:"acdb"

2. 这个点没有考虑到！如果字母已经出现过了的话，这个字母最多也就替换原来的位置，而且会覆盖之前的序列，是错的！！！跳过！（用一个set）
Input:"abacb"
Output:"acb"
Expected:"abc"

 
 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
public class Solution {
    public String removeDuplicateLetters(String s) {
        //可以先考虑数据结构，再思考具体解决方案
        Map<Character,Integer> map = new HashMap<>();
        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(map.containsKey(c))
                map.put(c,map.get(c)+1);
            else
                map.put(c,1);
        }
        boolean[] visited = new boolean[26]; //will contain if character (i+'a') is present in current result Stack

        for(int i = 0; i < s.length();i++){
            char c = s.charAt(i);
            map.put(c,map.get(c)-1);
            if(visited[c-'a']) {
                continue;
            }
            while(!stack.isEmpty() && stack.peek() > c && map.get(stack.peek()) > 0) {
                visited[stack.pop()-'a'] = false;
            }
            visited[c-'a'] = true;
            stack.push(c);
        }
        for(Character c : stack){
            sb.append(c);
        }
        return sb.toString();
    }
}
Greedy:
枚举字符串前缀，直到遇到首个唯一字符为止，从前缀中挑选出最小的字符作为首字符。

然后从剩余字符串中移除所有与首字母相同的字母。

重复此过程，直到选出所有唯一字符为止。
The runtime is O(26 * n) = O(n).
After determining the greedy choice s[i], we get a new string s' from s by
  1. removing all letters to the left of s[i],
  2. removing all s[i]'s from s.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
The runtime is O(26 * n) = O(n).

public class Solution {
    public String removeDuplicateLetters(String s) {
        int[] cnt = new int[26];
        int pos = 0; // the position for the smallest s[i]
        for (int i = 0; i < s.length(); i++) cnt[s.charAt(i) - 'a']++;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < s.charAt(pos)) pos = i;
            if (--cnt[s.charAt(i) - 'a'] == 0) break;
        }
        return s.length() == 0 ? "" : s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
    }
}

5.Closest Binary Search Tree Value II
Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.
Note:
  • Given target value is a floating point.
  • You may assume k is always valid, that is: k ≤ total nodes.
  • You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
Hint:
  1. Consider implement these two helper functions:
    1. getPredecessor(N), which returns the next smaller node to N.
    2. getSuccessor(N), which returns the next larger node to N.
  2. Try to assume that each node has a parent pointer, it makes the problem much easier.
  3. Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
  4. You would need two stacks to track the path in finding predecessor and successor node separately.
 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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
  List<Integer> res = new ArrayList<>();

  Stack<Integer> s1 = new Stack<>(); // predecessors
  Stack<Integer> s2 = new Stack<>(); // successors

  inorder(root, target, false, s1);
  inorder(root, target, true, s2);
  
  while (k-- > 0) {
    if (s1.isEmpty())
      res.add(s2.pop());
    else if (s2.isEmpty())
      res.add(s1.pop());
    else if (Math.abs(s1.peek() - target) < Math.abs(s2.peek() - target))
      res.add(s1.pop());
    else
      res.add(s2.pop());
  }
  
  return res;
}

// inorder traversal
void inorder(TreeNode root, double target, boolean reverse, Stack<Integer> stack) {
  if (root == null) return;

  inorder(reverse ? root.right : root.left, target, reverse, stack);
  // early terminate, no need to traverse the whole tree
  if ((reverse && root.val <= target) || (!reverse && root.val > target)) return;
  // track the value of current node
  stack.push(root.val);
  inorder(reverse ? root.left : root.right, target, reverse, stack);
}
}
O(logN)
public class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> ret = new LinkedList<>();
        Stack<TreeNode> succ = new Stack<>();
        Stack<TreeNode> pred = new Stack<>();
        initializePredecessorStack(root, target, pred);
        initializeSuccessorStack(root, target, succ);
        if(!succ.isEmpty() && !pred.isEmpty() && succ.peek().val == pred.peek().val) {
            getNextPredecessor(pred);
        }
        while(k-- > 0) {
            if(succ.isEmpty()) {
                ret.add(getNextPredecessor(pred));
            } else if(pred.isEmpty()) {
                ret.add(getNextSuccessor(succ));
            } else {
                double succ_diff = Math.abs((double)succ.peek().val - target);
                double pred_diff = Math.abs((double)pred.peek().val - target);
                if(succ_diff < pred_diff) {
                    ret.add(getNextSuccessor(succ));
                } else {
                    ret.add(getNextPredecessor(pred));
                }
            }
        }
        return ret;
    }

    private void initializeSuccessorStack(TreeNode root, double target, Stack<TreeNode> succ) {
        while(root != null) {
            if(root.val == target) {
                succ.push(root);
                break;
            } else if(root.val > target) {
                succ.push(root);
                root = root.left;
            } else {
                root = root.right;
            }
        }
    }

    private void initializePredecessorStack(TreeNode root, double target, Stack<TreeNode> pred) {
        while(root != null){
            if(root.val == target){
                pred.push(root);
                break;
            } else if(root.val < target){
                pred.push(root);
                root = root.right;
            } else{
                root = root.left;
            }
        }
    }
    
    private int getNextSuccessor(Stack<TreeNode> succ) {
        TreeNode curr = succ.pop();
        int ret = curr.val;
        curr = curr.right;
        while(curr != null) {
            succ.push(curr);
            curr = curr.left;
        }
        return ret;
    }

    private int getNextPredecessor(Stack<TreeNode> pred) {
        TreeNode curr = pred.pop();
        int ret = curr.val;
        curr = curr.left;
        while(curr != null) {
            pred.push(curr);
            curr = curr.right;
        }
        return ret;
    }
}

 6. Decode String
Given an encoded string, return it's decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].
Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".


 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 class Solution {
    public String decodeString(String s) {
        Stack<String> stack = new Stack<>();
        Stack<Integer> count = new Stack<>();
        int num = 0;StringBuilder sb = null;
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(Character.isDigit(c)){
                num = num*10 + c - '0';
            }else if(c == '['){
                //number is before
                if(sb!=null){
                    stack.push(sb.toString());
                    sb = null;
                }else{
                    stack.push("");
                }
                count.push(num);
                num = 0;
            }else if(c == ']'){
                int n = count.pop();
                String str = sb.toString();
                while(--n > 0){
                    sb.append(str);
                }                
                sb.insert(0,stack.pop());
                System.out.println((count.empty()?0:count.peek())+" "+sb.toString());
            }else{
                if(sb == null)
                    sb = new StringBuilder();
                sb.append(c);
            }
        }
        return sb == null? "":sb.toString();
    }
}


7. Ternary Expression Parser
Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression. You can always assume that the given expression is valid and only consists of digits 0-9, ?, :, T and F (T and F represent True and False respectively).
Note:
  1. The length of the given string is ≤ 10000.
  2. Each number will contain only one digit.
  3. The conditional expressions group right-to-left (as usual in most languages).
  4. The condition will always be either T or F. That is, the condition will never be a digit.
  5. The result of the expression will always evaluate to either a digit 0-9, T or F.
Example 1:
Input: "T?2:3"

Output: "2"

Explanation: If true, then result is 2; otherwise result is 3.
Example 2:
Input: "F?1:T?4:5"

Output: "4"

Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

             "(F ? 1 : (T ? 4 : 5))"                   "(F ? 1 : (T ? 4 : 5))"
          -> "(F ? 1 : 4)"                 or       -> "(T ? 4 : 5)"
          -> "4"                                    -> "4"
Example 3:

Input: "T?T?F:5:3"

Output: "F"

Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

             "(T ? (T ? F : 5) : 3)"                   "(T ? (T ? F : 5) : 3)"
          -> "(T ? F : 3)"                 or       -> "(T ? F : 5)"
          -> "F"                                    -> "F"


 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
public class Solution {
    public String parseTernary(String expression) {
        // why only judge on ?
        // we look from right to left, think how we do it when we compute
        // we ignore things except '?', when we meet '?', we look at nearby three elements
        // event through ?():(), this situation, we've already calculated result for things inside()
        // use stack to preserve previous solutions
        Stack<Character> stack = new Stack<>();
        for(int i = expression.length()-1; i>=0; i--){
            if(expression.charAt(i) == '?'){
                char t = stack.pop();
                stack.pop();
                char f = stack.pop();
                if(expression.charAt(i-1) == 'F'){
                    stack.push(f);
                }else {
                    stack.push(t);
                }
                i--;
            }else{
                stack.push(expression.charAt(i));
            }
        }
        return stack.pop()+"";
    }
}

8. Basic Calculator

Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:


"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23



 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
public class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int ans = 0;
        int sign = 1;
        int tmp = 0;
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(c == '('){
                stack.push(sign);
                stack.push(ans);
                sign = 1;
                ans = 0;
            }else if(c==')'){
                ans  += sign*tmp;
                ans = stack.pop() + stack.pop()*ans;
                tmp = 0;
            }else if(c == '+'){
                ans  += sign*tmp;
                sign = 1;
                tmp = 0;
            }else if (c == '-'){
                ans  += sign*tmp;
                sign = -1;
                tmp = 0;
            }else if(c == ' ') continue;
            else{
                tmp = tmp*10 + c-'0';
            }
        }
        ans  += sign*tmp;
        return ans;
    }
}

9. Simplify Path
Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public String simplifyPath(String path) {
        String[] strs = path.split("\\/");
        Stack<String> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for(String str: strs){
            if(str.equals(".")||str.equals(""))
                continue;
            else if(str.equals("..")){
                if(!stack.empty())
                    stack.pop();
            }else{
                stack.push(str);
            }
        }
        while(!stack.empty()){
            String str = stack.pop();
            sb.insert(0,"/"+str);
        }
        return sb.length()==0? "/": sb.toString();
        
    }
}


10. Flatten Nested List Iterator
Given a nested list of integers, implement an iterator to flatten it.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Example 1:
Given the list [[1,1],2,[1,1]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
Example 2:
Given the list [1,[4,[6]]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

 
 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
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    Stack<NestedInteger> stack;
    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new Stack<>();
        if(nestedList == null) return;
        for(int i = nestedList.size()-1; i>=0; i--){
            stack.push(nestedList.get(i));
        }
                    
    }

    @Override
    public Integer next() {
        return stack.pop().getInteger();
    }

    @Override
    public boolean hasNext() {
         while(!stack.empty() && !stack.peek().isInteger()){
            List<NestedInteger> nestedList = stack.pop().getList();
            for(int i = nestedList.size()-1; i>=0; i--){
                if(nestedList.get(i)!=null)
                    stack.push(nestedList.get(i));
            }
        }
        return !stack.empty();
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

11. 132 Pattern
Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.
Note: n will be less than 15,000.
Example 1:
Input: [1, 2, 3, 4]

Output: False

Explanation: There is no 132 pattern in the sequence.
Example 2:
Input: [3, 1, 4, 2]

Output: True

Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
Example 3:

Input: [-1, 3, 2, 0]

Output: True

Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].
http://www.cnblogs.com/grandyang/p/6081984.html
这道题给我们了一个数组，让我们找到132的模式，就是第一个数小于第二第三个数，且第三个数小于第二个数。那么我们就按顺序来找这三个数，首先我们来找第一个数，这个数需要最小，那么我们如果发现当前数字大于等于后面一个数字，我们就往下继续遍历，直到当前数字小于下一个数字停止。然后我们找第二个数字，这个数字需要最大，那么如果我们发现当前数字小于等于下一个数字就继续遍历，直到当前数字大雨下一个数字停止。最后就找第三个数字，我们验证这个数字是否在之前两个数字的中间，如果没有找到，我们就从第二个数字的后面一个位置继续开始重新找这三个数字，参见代码如下：


解法一：
复制代码
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        if (nums.size() <= 2) return false;
        int n = nums.size(), i = 0, j = 0, k = 0;
        while (i < n) {
            while (i < n - 1 && nums[i] >= nums[i + 1]) ++i;
            j = i + 1;
            while (j < n - 1 && nums[j] <= nums[j + 1]) ++j;
            k = j + 1;
            while (k < n) {
                if (nums[k] > nums[i] && nums[k] < nums[j]) return true;
                ++k;
            }
            i = j + 1;
        }
        return false;
    }
};
复制代码
下面这种方法利用来栈来做，既简洁又高效，思路是我们维护一个栈和一个变量third，其中mid就是第三个数字，栈里面按顺序放所有大于third的数字，那么我们在遍历的时候，如果当前数字大于third，我们直接返回true即可，因为已经找到了，注意我们应该从后往前遍历数组。如果当前数字大于栈顶元素，那么我们按顺序将栈顶数字取出，赋值给third，然后将该数字压入栈，这样保证了栈里的元素仍然都是大于third的，我们想要的顺序依旧存在，参见代码如下：

解法二：

复制代码
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int third = INT_MIN;
        stack<int> s;
        for (int i = nums.size() - 1; i >= 0; --i) {
            if (nums[i] < third) return true;
            else while (!s.empty() && nums[i] > s.top()) {
                third = s.top(); s.pop();
            }
            s.push(nums[i]);
        }
        return false;
    }
};
12 Remove K Digits
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:
  • The length of num is less than 10002 and will be ≥ k.
  • The given num does not contain any leading zero.
Example 1:
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
public class Solution {
    public String removeKdigits(String num, int k) {
        int len = num.length();
        //corner case
        if(k==len)        
            return "0";
            
        Stack<Character> stack = new Stack<>();
        int i =0;
        while(i<num.length()){
            //whenever meet a digit which is less than the previous digit, discard the previous one
            while(k>0 && !stack.isEmpty() && stack.peek()>num.charAt(i)){
                stack.pop();
                k--;
            }
            stack.push(num.charAt(i));
            i++;
        }
        
        // corner case like "1111"
        while(k>0){
            stack.pop();
            k--;            
        }
        
        //construct the number from the stack
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty())
            sb.append(stack.pop());
        sb.reverse();
        
        //remove all the 0 at the head
        while(sb.length()>1 && sb.charAt(0)=='0')
            sb.deleteCharAt(0);
        return sb.toString();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public String removeKdigits(String num, int k) {
       StringBuilder sb = new StringBuilder(num);
       return helper(sb,k);
    }
    public String helper(StringBuilder num, int k){
        if(k == num.length()) return "0";
        if(k == 0) return num.toString();
        int i = 0;
        while(i <  num.length()-1 && k > 0){
            if(num.charAt(i) > num.charAt(i+1)){
                num.deleteCharAt(i);
                if(i>0) i--;
                k--;
                continue;
            }
            i++;
        }
        while(k-->0) num.deleteCharAt(num.length()-1);
        String ans = num.toString().replaceAll("^0*","");
        return ans.length()==0?"0":ans;
    }
}

13. Evaluate Reverse Polish Notation'
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

 
 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
public class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        int ans = 0;
        for(int i = 0; i <tokens.length; i++){
            String str = tokens[i];
            if(isOperator(str)){
                int y = stack.pop();
                int x = stack.pop();
                stack.push(operate(x,y,str));
            }else{
                stack.push(Integer.valueOf(str));
            }
        }
        return stack.pop();
    }
    public boolean isOperator(String s){
        return s.equals("/") ||s.equals("*")||s.equals("-")||s.equals("+");
    }
    public int operate(int x, int y, String s){
        if(s.equals("/")){
            return x/y;
        }else if (s.equals("*")){
            return x*y;
        }else if(s.equals("-")){
            return x-y;      
        }else{
            return x+y;        
        }
    }
}

14. Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
         List<Integer>  ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) return ret; 
        stack.push(root);
        while(!stack.empty()){
            TreeNode cur = stack.pop();   
            ret.add(cur.val);
            if(cur.right!=null) stack.push(cur.right);
            if(cur.left!=null) stack.push(cur.left);
        }
        return ret;
    }
}

15. Binary Tree Inorder Traversal

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
         List<Integer>  ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) return ret; 
        TreeNode cur = root;
        while(!stack.empty()||cur!=null){
            while(cur!= null){
                stack.push(cur);
                cur= cur.left;
            }
            cur = stack.pop();
            ret.add(cur.val);
            cur = cur.right;
        }
        return ret;
    }
}




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer>  ret = new ArrayList<>();
        if(root == null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        Set<TreeNode> set = new HashSet<>();
        stack.push(root);
        while(!stack.empty()){
            TreeNode cur = stack.peek();
            if( (cur.left == null || set.contains(cur.left)) && (cur.right == null || set.contains(cur.right))){
                ret.add(cur.val);
                stack.pop();
                set.add(cur);
            }
            else{
                if(cur.right!=null)
                    stack.push(cur.right);
                if(cur.left!=null)
                    stack.push(cur.left);
            }
        }
        return ret;
    }
}
16. 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
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer>  ret = new ArrayList<>();
        if(root == null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(!stack.empty()||cur!=null){
            while(cur!=null){
                if(cur.right!=null)
                    stack.push(cur.right);
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode tmp = stack.pop();
            if(!stack.empty() && tmp.right == stack.peek()){
                cur = stack.pop();
                stack.push(tmp);
            }else{
                ret.add(tmp.val);
            }
            
        }
        return ret;
    }
}

17.Binary Search Tree Iterator
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

public class BSTIterator {
    
    private Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null){
            stack.push(cur);
            if(cur.left != null)
                cur = cur.left;
            else
                break;
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode node = stack.pop();
        TreeNode cur = node;
        // traversal right branch
        if(cur.right != null){
            cur = cur.right;
            while(cur != null){
                stack.push(cur);
                if(cur.left != null)
                    cur = cur.left;
                else
                    break;
            }
        }
        return node.val;
    }
}

18. Binary Tree Zigzag Level Order 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
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
         List<List<Integer>>  result = new ArrayList<List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null) return result;
        queue.add(root);
        List<Integer> level;
        while(!queue.isEmpty()){
            level = new ArrayList<>();
            int size = queue.size();
            for(int i =0;i < size;i++){
                TreeNode cur = queue.poll();
                if(result.size()%2 == 0)
                    level.add(cur.val);
                else
                     level.add(0,cur.val);
                if(cur.left!=null)queue.add(cur.left);
                if(cur.right!=null)queue.add(cur.right);
            }
            result.add(level);
        }
        return result;
    }
}

19. Verify Preorder Sequence in Binary Search Tree
Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.
You may assume each number in the sequence is unique.
Follow up:
Could you do it using only constant space complexity?
bool verifyPreorder(vector<int>& preorder){
    // using stack
    int sz = preorder.size();
    if(sz < 2) return true;
    stack<int> s;
    s.push(preorder[0]);
    int curr_p = INT_MIN;
    for(int i=1; i<sz; i++){ 
        if(s.empty() || preorder[i]<s.top()){ // if current node is less than stack top, then go to left subtree
            if(preorder[i]<curr_p) return false; 
            s.push(preorder[i]);
        }
        else{
            while(!s.empty() && s.top()<preorder[i]){ //find curr_p such that current node is right child of curr_p
                curr_p = s.top();
                s.pop();
            }
            s.push(preorder[i]);
        }
    }
    return true;
}

 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int preIdx = -1, min = Integer.MIN_VALUE;
        for(int val: preorder){
            if(val < min) return false;
            while(preIdx!=-1 && val > preorder[preIdx]){
                min = preorder[preIdx--];
            }
            preorder[++preIdx] = val;
        }
        return true;
    }
}



20. Verify Preorder Serialization of a Binary Tree
One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.
     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #
For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.
Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.
Each comma separated value in the string must be either an integer or a character '#' representing null pointer.
You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".
Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true
Example 2:
"1,#"
Return false
Example 3:
"9,#,#,1"
Return false

 

 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
public class Solution {
    class Node{
        String val;
        boolean left;
        public Node(String s){
            left = false;
            val = s;
        }
    }
    public boolean isValidSerialization(String preorder) {
        if(preorder.equals("#")) return true;
        Stack<Node> stack = new Stack<>();
        String[] strs = preorder.split(",");
        for(int i = 0 ; i < strs.length(); i++){
            String s = strs[i];
            if(c == '#'){
                if(stack.empty()) return false;
                while(!stack.empty() && stack.peek().left){
                    stack.pop();
                }
                if(!stack.empty())
                    stack.peek().left = true;
                if(stack.empty() && i <  preorder.length()-1)
                    return false;
            }
            else stack.push(new TreeNode(s));
        }
        return stack.empty();
    }
}



left visited using '#' as notation in stack
when we meet the leaf, we pop visited nodes from stack

 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public boolean isValidSerialization(String preorder) {
        if(preorder.equals("#")) return true;
        Stack<String> stack = new Stack<>();
        String[] strs = preorder.split(",");
        for(int i = 0 ; i < strs.length; i++){
            String s = strs[i];
            if(s.equals("#")){
                while(!stack.empty() && stack.peek().equals("#")){
                    stack.pop();
                    if(stack.empty()) return false;
                    stack.pop();
                }
            }
            stack.push(s);
        }
        return stack.size()==1&&stack.peek().equals("#");
    }
}

Some used stack. Some used the depth of a stack. Here I use a different perspective. In a binary tree, if we consider null as leaves, then
  • all non-null node provides 2 outdegree and 1 indegree (2 children and 1 parent), except root
  • all null node provides 0 outdegree and 1 indegree (0 child and 1 parent).
Suppose we try to build this tree. During building, we record the difference between out degree and in degree diff = outdegree - indegree. When the next node comes, we then decrease diff by 1, because the node provides an in degree. If the node is not null, we increase diff by 2, because it provides two out degrees. If a serialization is correct, diff should never be negative and diff will be zero when finished.

public boolean isValidSerialization(String preorder) {
    String[] nodes = preorder.split(",");
    int diff = 1;
    for (String node: nodes) {
        if (--diff < 0) return false;
        if (!node.equals("#")) diff += 2;
    }
    return diff == 0;
}

21. Implement Stack using Queues
O(n) pop/peek
class MyStack {
    Queue<Integer> q = new LinkedList<Integer>();
    
    // Push element x onto stack.
    public void push(int x) {
        q.add(x);
    }

    // Removes the element on top of the stack.
    public void pop() {
        int size = q.size();
        for(int i = 1; i < size; i++)
            q.add(q.remove());
        q.remove();
    }

    // Get the top element.
    public int top() {
        int size = q.size();
        for(int i = 1; i < size; i++)
            q.add(q.remove());
        int ret = q.remove();
        q.add(ret);
        return ret;
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return q.isEmpty();        
    }
}
o(n) push
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class MyStack {
    LinkedList<Integer> q = new LinkedList<>();
    public void push(int x) {
        q.add(x);
        for(int i = 0; i < q.size()-1; i++){
            q.add(q.remove());
        }
    }//0; 1,0; 2,1,0//
    // Removes the element from in front of queue.
    public void pop() {
      q.remove();
    }

    // Get the front element.
    public int top() {
        return q.getFirst();
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return q.isEmpty();
    }
}



22. Implement Queue using Stacks 


 2 stacks
one is correct order, the other is reversed

 
 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
class MyQueue {
    // Push element x to the back of queue.
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    public void push(int x) {
        stack1.push(x);
    }

    // Removes the element from in front of queue.
    public void pop() {
       peek();
       stack2.pop();
    }

    // Get the front element.
    public int peek() {
        if(!stack2.empty()) return stack2.peek();
         while(!stack1.empty()){
            stack2.push(stack1.pop());
        } 
        return stack2.peek();
        
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return stack1.empty() && stack2.empty();
    }
    //push 1->2->3
    //pop 3 (2,1)
    //push 4->5 
    //pop 5 (5,2,1)
}

23. Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public class Solution {
    public boolean isValid(String s) {
        //012
        Map<Character,Character> map = new HashMap<>();
        map.put('(',')');map.put('{','}');map.put('[',']');
        Stack<Character> stack = new Stack<>();
        for(int i =0 ;i < s.length();i++){
            char c = s.charAt(i);
            if(c == '('||c=='['||c=='{')
                stack.push(c);
            else{
                if(stack.empty() || map.get(stack.pop())!=c)return false;
            }
        }
        return stack.empty();
    }
}



24. minStack



发帖者 时间：
标签：

没有评论:

发表评论

订阅： 博文评论 (Atom)