Using Stack - Algorithm

Use stack to change operation order

LeetCode 232 - Implement Queue using Stacks
http://codercareer.blogspot.com/2013/02/no-39-stacks-sharing-array.html

Implement 3/k stacks in 1 array

LeetCode 20 - Valid Parentheses

X. Using stack
LeetCode 439 - Ternary Expression Parser
Recursion
http://hongzheng.me/leetcode/leetcode-439-ternary-expression-parser/

X. Using 2 stacks
Lintcode - Expression Tree Build
    public ExpressionTreeNode build(String[] expression) {
        Stack ops = new Stack<>();
        Stack data = new Stack<>();
        for( int i = 0; i < expression.length; i++) {
            String str = expression[i];
            if(str.equals("+") || str.equals("-") ||str.equals("*") ||str.equals("/")) {
                while(!ops.isEmpty() && operatorLevel(ops.peek().symbol) >= operatorLevel(str)) {
                    newNodeGtr(ops, data);
                }
                ops.push(new ExpressionTreeNode(str));
            }else if(str.equals("(")){
                ops.push(new ExpressionTreeNode(str));
            }else if(str.equals(")")) {
                while(!ops.isEmpty() && !ops.peek().symbol.equals("("))
                    newNodeGtr(ops, data);
                if(!ops.isEmpty()) 
                    ops.pop(); // pop the "("
            }else
                data.push(new ExpressionTreeNode(str));
        }

        while(!ops.isEmpty())
            newNodeGtr(ops, data);

        return data.isEmpty()? null : data.pop();
    }
Expression Evaluation

LeetCode 394 - Decode String
s = "3[a2[c]]", return "accaccacc".
    public String decodeString(String s) {
        Stack count = new Stack<>();
        Stack result = new Stack<>();
        int i = 0;
        result.push("");
        while (i < s.length()) {
            char ch = s.charAt(i);
            if (ch >= '0' && ch <= '9') {
                int start = i;
                while (s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') i++;
                count.push(Integer.parseInt(s.substring(start, i + 1)));
            } else if (ch == '[') {
                result.push("");
            } else if (ch == ']') {
                String str = result.pop();
                StringBuilder sb = new StringBuilder();
                int times = count.pop();
                for (int j = 0; j < times; j += 1) {
                    sb.append(str);
                }
                result.push(result.pop() + sb.toString());
            } else {
                result.push(result.pop() + ch);
            }
            i += 1;
        }
        return result.pop();
    }
- Using Recursion

X. Ordered stack
print the nearest larger element for each element.


LeetCode 32 - Longest Valid Parentheses
Largest Rectangular Area in a Histogram

LeetCode 84 - Largest Rectangle in Histogram
- Ordered Stack

Stack Reversal

LeetCode 71 - Simplify Path
- Using Double Queue LinkedList

LeetCode 385 - Mini Parser
- NestedInteger
- Using Stack


Design a deep iterator
private Stack iteratorStack = new Stack();
private Integer top = null;
    private Stack iteratorStack = new Stack();
    private Integer top = null;

    public DeepIterator(Iterable iterable){
        this.iteratorStack.push(iterable.iterator());
    }
    public boolean hasNext() {
        if(this.top != null) return true;

        while(!this.iteratorStack.isEmpty()) {
            Iterator tmpIterator = this.iteratorStack.peek();

            if(tmpIterator.hasNext()){
                Object tmp = tmpIterator.next();
                if(tmp instanceof Integer){
                    this.top = (Integer) tmp;
                    return true;
                } else if(tmp instanceof Iterable){
                    this.iteratorStack.push(((Iterable) tmp).iterator());
                } else {
                    throw new RuntimeException("Unsupported data type. ");
                }
            } else {
                this.iteratorStack.pop();
            }
        }
        return false;
    }

LeetCode 103 - Printing a Binary Tree in Zig Zag Level-Order
- Using two stacks
     if(d==0){
      if (node.left != null) next_layer.push(node.left);
      if (node.right != null) next_layer.push(node.right);
     }else{
      if (node.right != null) next_layer.push(node.right);
      if (node.left != null) next_layer.push(node.left);
     }
- Using DoubleQueue LinkedList
- Using DFS
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length, next[] = new int[n];
        Arrays.fill(next, -1);
        Stack stack = new Stack<>(); // index stack
        for (int i = 0; i < n * 2; i++) {
            int num = nums[i % n]; 
            while (!stack.isEmpty() && nums[stack.peek()] < num)
                next[stack.pop()] = num;
            if (i < n) stack.push(i);//
        }   
        return next;
    }


X. Ordered stack
Leetcode 316 - 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.
All characters in stack are increasing
public String removeDuplicateLetters(String sr) {

    int[] res = new int[26]; //will contain number of occurences of character (i+'a')
    boolean[] visited = new boolean[26]; //will contain if character (i+'a') is present in current result Stack
    char[] ch = sr.toCharArray();
    for(char c: ch){  //count number of occurences of character 
        res[c-'a']++;
    }
    Stack st = new Stack<>(); // answer stack
    int index;
    for(char s:ch){ 
        index= s-'a';
        res[index]--;   //decrement number of characters remaining in the string to be analysed
        if(visited[index]) //if character is already present in stack, dont bother
            continue;
        //if current character is smaller than last character in stack which occurs later in the string again
        //it can be removed and  added later e.g stack = bc remaining string abc then a can pop b and then c
        while(!st.isEmpty() && s'a'
]!=0){ visited[st.pop()-'a']=false; } st.push(s); //add current character and mark it as visitedvisited[index]=true; } StringBuilder sb = new StringBuilder(); //pop character from stack and build answer string from back while(!st.isEmpty()){ sb.insert(0,st.pop()); } return sb.toString(); }https://discuss.leetcode.com/topic/32259/java-solution-using-stack-with-comments/3
Use StringBuilder as the stack
    public String removeDuplicateLetters(String s) {
        
        int[] res = new int[26]; // will contain number of occurences of character (i+'a')
        boolean[] visited = new boolean[26]; // will contain if character ('a' + i) is present in current result Stack
        char[] ch = s.toCharArray();
        for(char c : ch){  // count number of occurences of character 
            res[c-'a']++;
        }
        StringBuilder sb = new StringBuilder();; // answer stack
        int index;
        for(char c : ch){ 
            index = c - 'a';
            res[index]--;   // decrement number of characters remaining in the string to be analysed
            if(visited[index]) // if character is already present in stack, dont bother
                continue;
            // if current character is smaller than last character in stack which occurs later in the string again
            // it can be removed and  added later e.g stack = bc remaining string abc then a can pop b and then c
            while( (sb.length() > 0) && c < sb.charAt(sb.length()-1) && res[sb.charAt(sb.length()-1)-'a']!=0){ 
                visited[sb.charAt(sb.length()-1) - 'a'] = false;
                sb.deleteCharAt(sb.length()-1);
            }
            sb.append(c); // add current character and mark it as visited
            visited[index] = true;
        }
        
        return sb.toString();
    
    }


Lintcode 126 - Max Tree
Given an integer array with no duplicates. A max tree building on this array is defined as follow:
  • The root is the maximum number in the array
  • The left subtree and right subtree are the max trees of the subarray divided by the root number.
Construct the max tree by the given array.
http://blog.welkinlan.com/2015/06/29/max-tree-lintcode-java/
    public TreeNode maxTree(int[] A) {
        // write your code here
        if (A == null || A.length == 0) {
            return null;
        }
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        for (int i = 0; i < A.length; i++) {
            TreeNode cur = new TreeNode(A[i]);
            while (!stack.isEmpty() && cur.val > stack.peek().val) {
                cur.left = stack.pop();
            }
            if (!stack.isEmpty()) {
                stack.peek().right = cur;
            }
            stack.push(cur);
        }
        TreeNode result = new TreeNode(0);
        while (!stack.isEmpty()) {
            result = stack.pop();
        }
        return result;
    }

LeetCode 84 - Largest Rectangle in Histogram
https://discuss.leetcode.com/topic/7599/o-n-stack-based-java-solution
    public int largestRectangleArea(int[] height) {
        int len = height.length;
        Stack s = new Stack();
        int maxArea = 0;
        for(int i = 0; i <= len; i++){
            int h = (i == len ? 0 : height[i]);
            if(s.isEmpty() || h >= height[s.peek()]){
                s.push(i);
            }else{
                int tp = s.pop();
                maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
                i--;
            }
        }
        return maxArea;
    }
Left, right array:
https://discuss.leetcode.com/topic/48127/java-o-n-left-right-arrays-solution-4ms-beats-96

Leetcode 85 - Maximal Rectangle
https://discuss.leetcode.com/topic/21772/my-java-solution-based-on-maximum-rectangle-in-histogram-with-explanation
public int maximalRectangle(char[][] matrix) {
    if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
    
    int[] height = new int[matrix[0].length];
    for(int i = 0; i < matrix[0].length; i ++){
        if(matrix[0][i] == '1') height[i] = 1;
    }
    int result = largestInLine(height);
    for(int i = 1; i < matrix.length; i ++){
        resetHeight(matrix, height, i);
        result = Math.max(result, largestInLine(height));
    }
    
    return result;
}

private void resetHeight(char[][] matrix, int[] height, int idx){
    for(int i = 0; i < matrix[0].length; i ++){
        if(matrix[idx][i] == '1') height[i] += 1;
        else height[i] = 0;
    }
}    

public int largestInLine(int[] height) {
    if(height == null || height.length == 0) return 0;
    int len = height.length;
    Stack s = new Stack();
    int maxArea = 0;
    for(int i = 0; i <= len; i++){
        int h = (i == len ? 0 : height[i]);
        if(s.isEmpty() || h >= height[s.peek()]){
            s.push(i);
        }else{
            int tp = s.pop();
            maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
            i--;
        }
    }
    return maxArea;
}
TODO
https://discuss.leetcode.com/topic/6650/share-my-dp-solution
http://www.voidcn.com/blog/meisen1124/article/p-4593005.html
https://discuss.leetcode.com/topic/36200/o-n-2-dp-java-solution
public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int[] left = new int[n]; // left boundary of histogram columns.
        int[] right = new int[n]; // right boundary of histogram columns.
        int[] height = new int[n]; // height of histogram columns.
        Arrays.fill(right, n);
        int area = 0;
        for (int i = 0; i < m; i++) {
            int l = 0, r = n;
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    height[j]++;
                    left[j] = Math.max(l, left[j]);
                }
                else {
                    l = j + 1;
                    height[j] = 0;
                    left[j] = 0;
                    right[j] = n;
                }
            }
            for (int j = n - 1; j >= 0; j--) {
                if (matrix[i][j] == '1') {
                    right[j] = Math.min(r, right[j]);
                    area = Math.max(area, height[j] * (right[j] - left[j]));
                }
                else {
                    r = j;
                }
            }
        }
        return area;
    }
LeetCode 42 - Trapping Rain Water
https://discuss.leetcode.com/topic/4939/a-stack-based-solution-for-reference-inspired-by-histogram
https://discuss.leetcode.com/topic/29113/java-with-stack-following-the-approach-similar-to-largest-rectangle-in-histogram
public int trap(int[] A) {
        if (A==null) return 0;
        Stack s = new Stack();
        int i = 0, maxWater = 0, maxBotWater = 0;
        while (i < A.length){
            if (s.isEmpty() || A[i]<=A[s.peek()]){
                s.push(i++);
            }
            else {
                int bot = s.pop();
                maxBotWater = s.isEmpty()? // empty means no il
                0:(Math.min(A[s.peek()],A[i])-A[bot])*(i-s.peek()-1);
                maxWater += maxBotWater;
            }
        }
        return maxWater;
    }
LeetCode 103 - Printing a Binary Tree in Zig Zag Level-Order
https://discuss.leetcode.com/topic/3318/my-ac-java-code
public List<List> zigzagLevelOrder(TreeNode root) {
    List<List> output = new ArrayList<List>();
    if (root == null) return output;
    Stack cur_layer = new Stack(); cur_layer.push(root);
    Stack next_layer = new Stack();
    List layer_output = new ArrayList();
    int d = 0; // 0: left to right; 1: right to left.
    
    while (!cur_layer.isEmpty()){
     TreeNode node = cur_layer.pop();
     layer_output.add(node.val);
     if(d==0){
      if (node.left != null) next_layer.push(node.left);
      if (node.right != null) next_layer.push(node.right);
     }else{
      if (node.right != null) next_layer.push(node.right);
      if (node.left != null) next_layer.push(node.left);
     }
     
     if (cur_layer.isEmpty()){
      output.add(layer_output);
      layer_output = new ArrayList();
      cur_layer = next_layer;
      next_layer = new Stack();;
      d ^= 1;
     }
    }
    return output;
}
BFS https://discuss.leetcode.com/topic/42184/java-easy-understand-recursive-methods-beats-96-attach-easy-bfs-methods
https://discuss.leetcode.com/topic/44739/java-iterative-and-recursive-solutions
  public List<List> zigzagLevelOrder(TreeNode root) {
    List<List> res = new ArrayList<>();
    if(root == null)
        return res;
    
    Queue q = new LinkedList<>();
    q.offer(root);
    int level = 1;
    while(!q.isEmpty()){
        LinkedList path = new LinkedList<>();
        int levelNums = q.size();
        
        for(int i = 0; i < levelNums; i++){
            root = q.poll();
            if(level % 2 != 0){
                path.add(root.val);
            }else{
                path.addFirst(root.val);
            }
            
            if(root.left != null)
                q.offer(root.left);
            if(root.right != null)
                q.offer(root.right);
        }
        res.add(path);
        level++;
    }
    
    return res;
}
https://discuss.leetcode.com/topic/40067/my-java-solution-beats-98
public List<List> zigzagLevelOrder(TreeNode root) {
    List<List> res = new ArrayList();
    travel(res, 0, root);
    return res;
}
private void travel(List<List> res, int level, TreeNode cur) {
    if (cur == null) return;
    if (res.size() <= level) {
        res.add(new ArrayList());
    }
    if (level % 2 == 0) {
        res.get(level).add(cur.val);
    }   else {
        res.get(level).add(0, cur.val);
    }
    travel(res, level + 1, cur.left);
    travel(res, level + 1, cur.right);
}

LeetCode 402 - 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.
http://www.voidcn.com/blog/yeqiuzs/article/p-6204756.html
public String removeKdigits(String num, int k) {
        Stack<Integer> stack = new Stack<Integer>();
        if (num.length() == 0 || num.length() <= k)
            return "0";

        for (int i = 0; i < num.length(); i++) {
            int cur = num.charAt(i) - '0';
            while (!stack.isEmpty() && cur < stack.peek()
                    && num.length() - i - 1 >= (num.length() - k) - stack.size()) {
                stack.pop();
            }
            if (stack.size()<num.length()-k)
                stack.push(cur);
        }

        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty())
            res.insert(0, stack.pop());

        while (res.length() > 0 && res.charAt(0) == '0')
            res.deleteCharAt(0);

        if (res.length() == 0)
            return "0";
        return res.toString();
    }


X. It should be intuitive for questions like parentheses
LeetCode 385 - Mini Parser
http://www.programcreek.com/2014/08/leetcode-mini-parser-java/
public NestedInteger deserialize(String s) {
 
    Stack<NestedInteger> stack = new Stack<NestedInteger>();
    String temp = "";
 
    for(char c: s.toCharArray()){
        switch(c){
            case '[':
                stack.push(new NestedInteger()); //start a new NI
                break;
 
            case ']':
                if(!temp.equals("")){
                    stack.peek().add(new NestedInteger(Integer.parseInt(temp))); //add NI to parent
                    temp="";
                }
 
                NestedInteger top = stack.pop();
                if(!stack.empty()){
                    stack.peek().add(top);
                }else{
                    return top;
                }
 
                break;
 
            case ',':
                if(!temp.equals("")){
                    stack.peek().add(new NestedInteger(Integer.parseInt(temp)));//add NI to parent
                    temp="";
                }
 
                break;
 
            default:
                temp += c;
        }
    }
 
    if(!temp.equals("")){
        return new NestedInteger(Integer.parseInt(temp));
    }
 
    return null;
}

X. Recursive version
https://discuss.leetcode.com/topic/54277/short-java-recursive-solution
https://discuss.leetcode.com/topic/54407/java-recursive-solution-one-scan-clean-easy-to-understand
    public NestedInteger deserialize(String s) {
        if (s.charAt(0) != '[') return new NestedInteger(Integer.parseInt(s));
        NestedInteger result = new NestedInteger();
        helper(s, 1, result);
        return result;
    }

    private int helper(String s, int idx, NestedInteger parent) {
        int l = idx, r = idx;
        while (r < s.length()) {
            String num = s.substring(l, r);
            if (s.charAt(r) == '[') {
                NestedInteger child = new NestedInteger();
                parent.add(child);
                r = helper(s, r + 1, child);
                l = r;
            } else if (s.charAt(r) == ']') {
                if (!num.isEmpty()) parent.add(new NestedInteger(Integer.valueOf(num)));
                return r + 1;
            } else if (s.charAt(r) == ',') {
                if (!num.isEmpty()) parent.add(new NestedInteger(Integer.valueOf(num)));
                r++;
                l = r;
            } else {
                r++;
            }
        }
        return s.length();
    }


LeetCode 388 - Longest Absolute File Path
Suppose we abstract our file system by a string in the following manner:
The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:
dir
    subdir1
    subdir2
        file.ext


The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.
https://discuss.leetcode.com/topic/55561/two-different-solutions-in-java-using-stack-and-hashmap
    public int lengthLongestPath(String input) {
        ArrayDeque stack = new ArrayDeque<>();
        int result = 0;
        for (String s : input.split("\n")) {
            int level = s.lastIndexOf("\t") + 1;
            while (stack.size() != level) {
                stack.pop();
            }
            int len = s.length() - level; //s.substring(level).length();
            if (stack.isEmpty()) {
                stack.push(len);
            } else {
                stack.push(stack.peek() + len + 1);
            }
            if (s.contains(".")) {
                result = Math.max(result, stack.peek());
            }
        }
        return result;
    }
X. Using HashMap
    public int lengthLongestPath2(String input) {
        HashMap hashMap = new HashMap<>();
        hashMap.put(0, 0);
        int result = 0;
        for (String s : input.split("\n")) {
            int level = s.lastIndexOf("\t") + 1;
            int len = s.length() - level; //s.substring(level).length();
            if (s.contains(".")) {
                result = Math.max(result, hashMap.get(level) + len);
            } else {
                hashMap.put(level + 1, hashMap.get(level) + len + 1);
            }
        }
        return result;
    }


Post a Comment

Labels

Java (159) Lucene-Solr (110) All (58) Interview (58) J2SE (53) Algorithm (43) Soft Skills (36) Eclipse (34) Code Example (31) Linux (24) JavaScript (23) Spring (22) Windows (22) Web Development (20) Nutch2 (18) Tools (18) Bugs (17) Debug (15) Defects (14) Text Mining (14) J2EE (13) Network (13) PowerShell (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) UIMA (9) html (9) Dynamic Languages (8) Http Client (8) Maven (8) Security (8) Trouble Shooting (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) Problem Solving (7) ANT (6) Coding Skills (6) Database (6) Scala (6) Shell (6) css (6) Algorithm Series (5) Cache (5) IDE (5) Lesson Learned (5) Programmer Skills (5) System Design (5) Tips (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Python (4) Spark (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Firefox (2) Google Drive (2) Gson (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Troubleshooting (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts