Sunday, August 14, 2016

LeetCode 385 - Mini Parser


https://www.hrwhisper.me/leetcode-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.
X. Using Stack
http://www.programcreek.com/2014/08/leetcode-mini-parser-java/
http://blog.csdn.net/yeqiuzs/article/details/52208388
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;
}

由于没有空格,所以第一个字母不是'[‘的说明只有一个数字。直接返回NestedInteger(int(s))
接下来,用一个栈来维护,对于左括号[的,当前的NestedInteger 进栈,对于右括号,当前数字放入NestedInteger 栈不为空则把栈顶的NestedInteger添加当前的NestedInteger,并且出栈。
http://bookshadow.com/weblog/2016/08/15/leetcode-mini-parser/
http://wisim.me/leetcode/2016/08/18/LeetCode_MinParser.html

Use StringBuilder
http://www.jianshu.com/p/4578be7c2270
    public NestedInteger deserialize(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }

        if (s.charAt(0) != '[') {
            return new NestedInteger(Integer.parseInt(s));
        }

        Stack<NestedInteger> st = new Stack<NestedInteger>();
        String temp = "";
        for (int i = 0; i < s.length(); i++) {
            char curr = s.charAt(i);
            switch (curr) {
                case '[':
                    st.push(new NestedInteger());
                    break;
                case ']':
                    if (temp.length() != 0) {
                        st.peek().add(new NestedInteger(Integer.parseInt(temp)));
                        temp = "";
                    }               
                    if (st.size() > 1) {
                        NestedInteger node = st.pop();
                        st.peek().add(node);
                    }
                    break;
                case ',':
                    if (temp.length() != 0) {
                        st.peek().add(new NestedInteger(Integer.parseInt(temp)));
                        temp = "";
                    }
                    break;
                default:
                    temp = temp + curr;
                    break;
            }
        }

        return st.pop();
    }
http://buttercola.blogspot.com/2015/11/airbnb-mini-parser.html
http://yuanhsh.iteye.com/blog/2230314
  private static class NestedIntList {
    private int value;
    private boolean isNumber;
    private List<NestedIntList> intList;
     
    // Constructor to construct a number
    public NestedIntList(int value) {
      this.value = value;
      isNumber = true;
    }
     
    // Constructor to construct a list
    public NestedIntList() {
      intList = new ArrayList<>();
      isNumber = false;
    }
     
    public void add(NestedIntList num) {
      this.intList.add(num);
    }
     
    public NestedIntList miniParser(String s) {
      if (s == null || s.length() == 0) {
        return null;
      }
       
      // Corner case "123"
      if (s.charAt(0) != '[') {
        int num = Integer.parseInt(s);
        return new NestedIntList(num);
      }
       
      int i = 0;
      int left = 1;
      Stack<NestedIntList> stack = new Stack<>();
      NestedIntList result = null;
       
      while (i < s.length()) {
        char c = s.charAt(i);
        if (c == '[') {
          NestedIntList num = new NestedIntList();
          if (!stack.isEmpty()) {
            stack.peek().add(num);
          }
          stack.push(num);
          left = i + 1;
        } else if (c == ',' || c == ']') {
          if (left != i) {
            int value = Integer.parseInt(s.substring(left, i));
            NestedIntList num = new NestedIntList(value);
            stack.peek().add(num);
          }
          left = i + 1;
           
          if (c == ']') {
            result = stack.pop();
          }
        }
         
        i++;
      }
       
      return result;
    }
     
    public String toString() {
      if (this.isNumber) {
        return this.value + "";
      } else {
        return this.intList.toString();
      }
    }
  }

http://blog.csdn.net/yeqiuzs/article/details/52208388
用栈维护一个包含关系,类似于用栈维护带 '(' 的表达式。
思路不难想到,有个坑爹的细节要注意:添加一个数到list type的nestedInteger时 要将该数封装为integer type的NestedInteger,然后用add方法添加该nestedInteger,不能直接用setInteger,否则会把list type的nestedInteger定义为一个integer type,会出错。
还可以用递归来做,思路大致是:没处理完一个token,遇到 [  递归处理 返回该层list结尾下标。好像有点麻烦。。留坑日后待填。
  1. public NestedInteger deserialize(String s) {  
  2.     Stack<NestedInteger> stack = new Stack<NestedInteger>();  
  3.     String tokenNum = "";  
  4.   
  5.     for (char c : s.toCharArray()) {  
  6.         switch (c) {  
  7.         case '['://[代表一个list  
  8.             stack.push(new NestedInteger());  
  9.             break;  
  10.         case ']'://list结尾  
  11.             if (!tokenNum.equals(""))//前面token为数字   
  12.                 stack.peek().add(new NestedInteger(Integer.parseInt(tokenNum)));//将数字加入到本层list中  
  13.             NestedInteger ni = stack.pop();//本层list结束  
  14.             tokenNum = "";  
  15.             if (!stack.isEmpty()) {//栈内有更高层次的list  
  16.                 stack.peek().add(ni);  
  17.             } else {//栈为空,遍历到字符串结尾  
  18.                 return ni;  
  19.             }  
  20.             break;  
  21.         case ',':  
  22.             if (!tokenNum.equals("")) //将数字加入到本层list中  
  23.                 stack.peek().add(new NestedInteger(Integer.parseInt(tokenNum)));  
  24.             tokenNum = "";  
  25.             break;  
  26.         default:  
  27.             tokenNum += c;  
  28.         }  
  29.     }  
  30.     if (!tokenNum.equals(""))//特殊case: 如果字符串只包含数字的情况  
  31.         return new NestedInteger(Integer.parseInt(tokenNum));  
  32.     return null;  
  33. }  

我们也可以使用迭代的方法来做,这样就需要使用栈来辅助,变量start记录起始位置,我们遍历字符串,如果遇到'[',我们给栈中加上一个空的NestInteger,如果遇到的字符数逗号或者']',如果i>start,那么我们给栈顶元素调用add来新加一个NestInteger,初始化参数传入start到i之间的子字符串转为的整数,然后更新start=i+1,当遇到的']'时,如果此时栈中元素多于1个,那么我们将栈顶元素取出,加入新的栈顶元素中通过调用add函数
    NestedInteger deserialize(string s) {
        if (s.empty()) return NestedInteger();
        if (s[0] != '[') return NestedInteger(stoi(s));
        stack<NestedInteger> st;
        int start = 1;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '[') {
                st.push(NestedInteger());
                start = i + 1;
            } else if (s[i] == ',' || s[i] == ']') {
                if (i > start) {
                    st.top().add(NestedInteger(stoi(s.substr(start, i - start))));
                }
                start = i + 1;
                if (s[i] == ']') {
                    if (st.size() > 1) {
                        NestedInteger t = st.top(); st.pop();
                        st.top().add(t);
                    }
                }
            }
        }
        return st.top();
    }
X. Recusive Version
https://discuss.leetcode.com/topic/54407/java-recursive-solution-one-scan-clean-easy-to-understand
  1. if '[', construct a new NestedInteger;
  2. if ']', add the number before ']' if it exists, the character before ']' must be a number or ']';
  3. if ',', add the number before ',' if it exists, the character before ',' must be a number or ']';
  4. if a number, just add the right pointer.
    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);//don't do here
            if (s.charAt(r) == '[') {
                NestedInteger child = new NestedInteger();
                parent.add(child);
                r = helper(s, r + 1, child);
                l = r;
            } else if (s.charAt(r) == ']') { // get num here
                if (!num.isEmpty()) parent.add(new NestedInteger(Integer.valueOf(num)));
                return r + 1;
            } else if (s.charAt(r) == ',') {//get num here
                if (!num.isEmpty()) parent.add(new NestedInteger(Integer.valueOf(num)));
                r++;
                l = r;
            } else {
                r++;
            }
        }
        return s.length();
    }
http://www.cnblogs.com/grandyang/p/5771434.html
我们可以先用递归来做,思路是,首先判断s是否为空,为空直接返回,不为空的话看首字符是否为'[',是的话说明s为一个整数,我们直接返回结果。如果首字符是'[',且s长度小于等于2,说明没有内容,直接返回结果。反之如果s长度大于2,我们从i=1开始遍历,我们需要一个变量start来记录某一层的其实位置,用cnt来记录跟其实位置是否为同一深度,cnt=0表示同一深度,由于中间每段都是由逗号隔开,所以当我们判断当cnt为0,且当前字符是逗号或者已经到字符串末尾了,我们把start到当前位置之间的字符串取出来递归调用函数,把返回结果加入res中,然后start更新为i+1。如果遇到'[',计数器cnt自增1,若遇到']',计数器cnt自减1
    NestedInteger deserialize(string s) {
        if (s.empty()) return NestedInteger();
        if (s[0] != '[') return NestedInteger(stoi(s));
        if (s.size() <= 2) return NestedInteger();
        NestedInteger res;
        int start = 1, cnt = 0;
        for (int i = 1; i < s.size(); ++i) {
            if (cnt == 0 && (s[i] == ',' || i == s.size() - 1)) {
                res.add(deserialize(s.substr(start, i - start)));
                start = i + 1;
            } else if (s[i] == '[') ++cnt;
            else if (s[i] == ']') --cnt;
        }
        return res;
    }

X. Recursive version 2
https://discuss.leetcode.com/topic/59029/short-and-clean-java-recursive-solution-with-explanation
Using the "lvl" variable to track if we are inside an inner integer.
Using lIndex to track the leftmost start position.
Every time the program hit the "[" increase lvl, and decrease lvl when hit "]"
When the program meets ","
If lvl != 0, ignore the "," since we are inside a nested integer
else do recursive call ,add the result to the current list and move lIndex.
[ [abc, [xy]] , def, [qqq] ]
ni.add(myDeserialize("[abc, [xy]]"));
ni.add(myDeserialize("def");
ni.add(myDeserialize("[qqq]");
public NestedInteger deserialize(String s) {
    if (s.length() == 0)    return new NestedInteger();
    return myDeserialize(s, 0, s.length()-1);
}

private NestedInteger myDeserialize(String s, int start, int end) {
    if (s.charAt(start) != '[') 
        return new NestedInteger(Integer.valueOf(s.substring(start, end+1)));

    NestedInteger ni = new NestedInteger();
    int lvl = 0, lIndex = start+1;

    for (int i=start+1 ; i<=end-1 ; ++i) {
        char ch = s.charAt(i);
        if (ch == '[')  ++lvl;
        else if (ch == ']') --lvl; 
        else if (ch == ',' && lvl == 0) {
            ni.add(myDeserialize(s, lIndex, i-1));
            lIndex = i + 1;
        }
    }
    if (lIndex <= end-1) {
        ni.add(myDeserialize(s, lIndex, end-1));
    }
    return ni;        
}
https://discuss.leetcode.com/topic/54277/short-java-recursive-solution
Just for people who try this approach instead of stack. This takes much more time than stack as the depth of elements grow. If you would like to reduce time complexity, use stack as a space trade-off for time.
    public NestedInteger deserialize(String s) {
        NestedInteger ret = new NestedInteger();
        if (s == null || s.length() == 0) return ret;
        if (s.charAt(0) != '[') {
            ret.setInteger(Integer.parseInt(s));
        }
        else if (s.length() > 2) {
            int start = 1, count = 0;
            for (int i = 1; i < s.length(); i++) {
                char c = s.charAt(i);
                if (count == 0 && (c == ',' || i == s.length() - 1)) {
                    ret.add(deserialize(s.substring(start, i)));
                    start = i + 1;
                }
                else if (c == '[') count++;
                else if (c == ']') count--;
            }
        }
        return ret;
    }
https://discuss.leetcode.com/topic/55872/very-short-recursive-solution
    NestedInteger parse(string& s, int& i) {
      if(s[i]=='[') {
          ++i;
          NestedInteger list;
          while(s[i] != ']') {
              list.add(parse(s,i));
              if(s[i] ==',') ++i;
          }
          ++i;
          return list;
      } else {                       
        int sum = 0;
        int sign=1;
        if(s[i] == '-'){ sign = -1; ++i;}
        while(isdigit(s[i])) { sum *= 10; sum+= s[i]-'0'; ++i;}
          return NestedInteger(sum*sign);
      }
    }
    NestedInteger deserialize(string s) {
        int i = 0;
        return parse(s, i);
    }
https://discuss.leetcode.com/topic/54274/java-10-ms-while-loop-recursion-one-scan

https://discuss.leetcode.com/topic/54268/straightforward-java-solution-with-explanation-and-a-simple-implementation-of-nestedinteger-for-your-ease-of-testing
class NestedInteger {
    private List<NestedInteger> list;
    private Integer integer;
    
    public NestedInteger(List<NestedInteger> list){
        this.list = list;
    }
    
    public void add(NestedInteger nestedInteger) {
        if(this.list != null){
            this.list.add(nestedInteger);
        } else {
            this.list = new ArrayList();
            this.list.add(nestedInteger);
        }
    }

    public void setInteger(int num) {
        this.integer = num;
    }

    public NestedInteger(Integer integer){
        this.integer = integer;
    }

    public NestedInteger() {
        this.list = new ArrayList();
    }

    public boolean isInteger() {
        return integer != null;
    }

    public Integer getInteger() {
        return integer;
    }

    public List<NestedInteger> getList() {
        return list;
    }
    
    public String printNi(NestedInteger thisNi, StringBuilder sb){
        if(thisNi.isInteger()) {
            sb.append(thisNi.integer);
            sb.append(",");
        }
        sb.append("[");
        for(NestedInteger ni : thisNi.list){
            if(ni.isInteger()) {
                sb.append(ni.integer);
                sb.append(",");
            }
            else {
                printNi(ni, sb);
            }
        }
        sb.append("]");
        return sb.toString();
    }
}



No comments:

Post a Comment

Labels

GeeksforGeeks (976) Algorithm (811) LeetCode (654) to-do (599) Review (362) Classic Algorithm (334) Classic Interview (298) Dynamic Programming (263) Google Interview (233) LeetCode - Review (233) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (119) Bit Algorithms (110) Cracking Coding Interview (110) Smart Algorithm (109) Math (91) HackerRank (85) Lintcode (83) Binary Search (73) Graph Algorithm (73) Greedy Algorithm (61) Interview Corner (61) Binary Tree (58) List (58) DFS (56) Algorithm Interview (53) Advanced Data Structure (52) Codility (52) ComProGuide (52) LeetCode - Extended (47) USACO (46) Geometry Algorithm (45) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Jobdu (39) Interval (38) Recursive Algorithm (38) Stack (38) String Algorithm (38) Binary Search Tree (37) Knapsack (37) Codeforces (36) Introduction to Algorithms (36) Matrix (36) Must Known (36) Beauty of Programming (35) Sort (35) Space Optimization (34) Array (33) Trie (33) prismoskills (33) Backtracking (32) Segment Tree (32) Union-Find (32) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Data Structure Design (29) Company-Zenefits (28) Microsoft 100 - July (28) to-do-must (28) Random (27) Sliding Window (27) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Hash (22) Queue (22) DFS + Review (21) TopCoder (21) Binary Indexed Trees (20) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Pre-Sort (20) Company-Facebook (19) UVA (19) Probabilities (18) Follow Up (17) Codercareer (16) Company-Uber (16) Game Theory (16) Heap (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Iterator (15) Merge Sort (15) O(N) (15) Bisection Method (14) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Codechef (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) KMP (12) Long Increasing Sequence(LIS) (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Ordered Stack (11) Princeton (11) Tree DP (11) 挑战程序设计竞赛 (11) Binary Search - Bisection (10) Company - Microsoft (10) Company-Airbnb (10) Euclidean GCD (10) Facebook Hacker Cup (10) HackerRank Easy (10) Reverse Thinking (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) X Sum (10) Coin Change (9) Divide and Conquer (9) Lintcode - Review (9) Mathblog (9) Max-Min Flow (9) Stack Overflow (9) Stock (9) Two Pointers (9) Book Notes (8) Bottom-Up (8) DP-Space Optimization (8) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) Suffix Tree (8) System Design (8) Tech-Queries (8) Time Complexity (8) Use XOR (8) 穷竭搜索 (8) Algorithm Problem List (7) DFS+BFS (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Linked List (7) Longest Common Subsequence(LCS) (7) Math-Divisible (7) Miscs (7) O(1) Space (7) Probability DP (7) Radix Sort (7) Simulation (7) Xpost (7) n00tc0d3r (7) 蓝桥杯 (7) Bucket Sort (6) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) How To (6) Interviewstreet (6) Kadane’s Algorithm (6) Knapsack - MultiplePack (6) Level Order Traversal (6) Manacher (6) Minimum Spanning Tree (6) One Pass (6) Programming Pearls (6) Quick Select (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Suffix Array (6) Threaded (6) reddit (6) AI (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Crazyforcode (5) DFS+Cache (5) DP-Multiple Relation (5) DP-Print Solution (5) Dutch Flag (5) Fast Slow Pointers (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Inversion (5) Java (5) Kadane - Extended (5) Matrix Chain Multiplication (5) Microsoft Interview (5) Morris Traversal (5) Pruning (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sweep Line (5) Traversal Once (5) TreeMap (5) jiuzhang (5) to-do-2 (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Anagram (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Company-Amazon (4) Consistent Hash (4) Convex Hull (4) Cycle (4) DP-Include vs Exclude (4) Dijkstra (4) Distributed (4) Eulerian Cycle (4) Flood fill (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) Left and Right Array (4) MinMax (4) Multiple Data Structures (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Pre-Sum (4) Probability (4) Programcreek (4) Quick Sort (4) Spell Checker (4) Stock Maximize (4) Subsets (4) Sudoku (4) Symbol Table (4) TreeSet (4) Triangle (4) Water Jug (4) Word Ladder (4) algnotes (4) fgdsb (4) 最大化最小值 (4) A Star (3) Abbreviation (3) Algorithm - Brain Teaser (3) Algorithm Design (3) Anagrams (3) B Tree (3) Big Data Algorithm (3) Binary Search - Smart (3) Caterpillar Method (3) Coins (3) Company - Groupon (3) Company - Indeed (3) Cumulative Sum (3) DP-Fill by Length (3) DP-Two Variables (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Edit Distance (3) Expression (3) Finite Automata (3) Forward && Backward Scan (3) Github (3) GoLang (3) Include vs Exclude (3) Joseph (3) Jump Game (3) Knapsack-多重背包 (3) LeetCode - Bit (3) LeetCode - TODO (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Maze (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Stack - Smart (3) State Machine (3) Streaming Algorithm (3) Subset Sum (3) Subtree (3) Transform Tree (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Search (3) bookkeeping (3) codebytes (3) Activity Selection Problem (2) Advanced Algorithm (2) AnAlgorithmADay (2) Application of Algorithm (2) Array Merge (2) BOJ (2) BT - Path Sum (2) Balanced Binary Search Tree (2) Bellman Ford (2) Binomial Coefficient (2) Bit Mask (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Branch and Bound Method (2) Clock (2) Codesays (2) Company - Baidu (2) Complete Binary Tree (2) DFS+BFS, Flood Fill (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-Output Solution (2) DP-Slide Window Gap (2) DP-i-k-j (2) DP-树形 (2) Distributed Algorithms (2) Divide and Conqure (2) Doubly Linked List (2) GoHired (2) Graham Scan (2) Graph - Bipartite (2) Graph BFS+DFS (2) Graph Coloring (2) Graph-Cut Vertices (2) Hamiltonian Cycle (2) Huffman Tree (2) In-order Traverse (2) Include or Exclude Last Element (2) Information Retrieval (2) Interview - Linkedin (2) Invariant (2) Islands (2) Knuth Shuffle (2) LeetCode - Recursive (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) MST (2) MST-Kruskal (2) Math-Remainder Queue (2) Matrix Power (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Palindromic (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) Shuffle (2) Sieve of Eratosthenes (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Stream (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Word Break (2) Word Graph (2) Word Trie (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - How To (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary Tree Variant (1) Bipartite (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Bug Free Code (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular Buffer (1) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Snapchat (1) Company-Yelp (1) Compression Algorithm (1) Concurrency (1) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS-Matrix (1) DP - Probability (1) DP Fill Diagonal First (1) DP-Difficult (1) DP-End with 0 or 1 (1) DP-Fill Diagonal First (1) DP-Graph (1) DP-Left and Right Array (1) DP-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Optimization (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) Database (1) Detect Negative Cycle (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Duplicate (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (1) Game (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) HOJ (1) Hanoi (1) Hard Algorithm (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Inorder-Reverse Inorder Traverse Simultaneously (1) Interpolation search (1) Interview (1) Interview - Easy (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Kosaraju’s algorithm (1) Kruskal (1) Kruskal MST (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode Diffcult (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Local MinMax (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Median (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Successor (1) Offline Algorithm (1) PAT (1) Parent-Only Tree (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) Probabilistic Data Structure (1) Proof (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Regular Expression (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie + DFS (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) Yahoo Interview (1) ZOJ (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts