Wednesday, February 24, 2016

LeetCode 95 - Unique Binary Search Trees II


https://leetcode.com/problems/unique-binary-search-trees-ii/
Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
Related LeetCode 96 - Unique Binary Search Trees
X. DFS
https://discuss.leetcode.com/topic/8410/divide-and-conquer-f-i-g-i-1-g-n-i
I just add an HashMap as the cache, but I'm wondering why the algorithm costs more time.
I would say the time complexity would be exponential. Since it can be found out from his code that T(n) = 2*(T(n-1) + T(n-2) + ... + T(1) + T(0)), T(n) should equal to $O(2^n)$
http://n00tc0d3r.blogspot.com/2013/07/unique-binary-search-trees_6.html
Think it in a deductive way:
  • n=1, one unique BST.
  • n=2, pick one value, and the one remaining node can be built as one BST, i.e. Two BSTs.
  • ... ...
  • n=k, pick one value i, and split the remaining values to two groups: [1 .. i-1] goes to left subtree and [i+1 .. n] goes to right subtree. Then the problem becomes to construct BSTs with left subtree from BST(1, i-1) and right subtree from BST(i+1, n), where BST(1, i-1) and BST(i+1, n) has been computed in previous iterations.
It is easy to get to a recursive solution:
  • Given a range [l .. r], if l > r, return a list containing an empty tree.
  • Otherwise, for each value k between l and r, inclusively
    • recursively compute BSTs in range [l .. k-1] and range [k+1 .. r]
    • construct BSTs with root of k, left subtree from BST(1, i-1) and right subtree from BST(i+1, n).
This algorithm runs in exponential time (much greater then the actual total count of unique BSTs) since we recompute BSTs in subrange [i .. j] repeatedly.
private ArrayList<TreeNode> genSubTrees(int l, int r) {  
   ArrayList<TreeNode> trees = new ArrayList<TreeNode>();  
   if (l > r) { // return an empty tree 
     trees.add(null);  
   } else {  
     for (int i=l; i<=r; ++i) {  
       ArrayList<TreeNode> lefts = genSubTrees(l, i-1);  
       ArrayList<TreeNode> rights = genSubTrees(i+1, r);  
       for (TreeNode left : lefts) {  
         for (TreeNode right : rights) {  
           TreeNode root = new TreeNode(i);  
           root.left = left;  
           root.right = right;  
           trees.add(root);  
         }  
       }  
     }  
   }  
   return trees;  
 }  
 public ArrayList<TreeNode> generateTrees(int n) {  
   return genSubTrees(1, n);  
 } 

I start by noting that 1..n is the in-order traversal for any BST with nodes 1 to n. So if I pick i-th node as my root, the left subtree will contain elements 1 to (i-1), and the right subtree will contain elements (i+1) to n. I use recursive calls to get back all possible trees for left and right subtrees and combine them in all possible ways with the root.
    public List<TreeNode> generateTrees(int n) {
        
        return genTrees(1,n);
    }
        
    public List<TreeNode> genTrees (int start, int end)
    {

        List<TreeNode> list = new ArrayList<TreeNode>();

        if(start>end)
        {
            list.add(null);
            return list;
        }
        
        if(start == end){
            list.add(new TreeNode(start));
            return list;
        }
        
        List<TreeNode> left,right;
        for(int i=start;i<=end;i++)
        {
            
            left = genTrees(start, i-1);
            right = genTrees(i+1,end);
            
            for(TreeNode lnode: left)
            {
                for(TreeNode rnode: right)
                {
                    TreeNode root = new TreeNode(i);
                    root.left = lnode;
                    root.right = rnode;
                    list.add(root);
                }
            }
                
        }
        
        return list;
    }
There is shared sub problem, but generate method is called every time. So no need to clone at all
public List<TreeNode> generateTrees(int n) {
    return genTreeList(1,n);
}

private List<TreeNode> genTreeList (int start, int end) {
    List<TreeNode> list = new ArrayList<TreeNode>(); 
    if (start > end) {
        list.add(null);
    }
    for(int idx = start; idx <= end; idx++) {
        List<TreeNode> leftList = genTreeList(start, idx - 1);
        List<TreeNode> rightList = genTreeList(idx + 1, end);
        for (TreeNode left : leftList) {
            for(TreeNode right: rightList) {
                TreeNode root = new TreeNode(idx);
                root.left = left;
                root.right = right;
                list.add(root);
            }
        }
    }
    return list;
}

X. DP

https://discuss.leetcode.com/topic/12559/java-dp-solution-and-brute-force-recursive-solution
Then @6219221 reminded me it is unnecessary to create the BSTs with all brand new nodes.
Assume you have a list of all BSTs with values from 1 to n-1, every possible way to insert value n only involves changing the right tree (root inclusive) because n is always greater than root.val and the left subtree structure is fixed. So all we gotta do is to create a new copy of the right part of the tree and point the new root.left to the original left subtree. This way we reuse the left tree, which saves time and space.
How to insert Node n into the right subtree?
Given any BST on the n - 1 level, it will be only valid to put n on the root.right, root.right.right or root.right.....right locations and then move the right subtree of n.right...right to become the left child of n, in order to keep n on the right-most position as the greatest value in the tree.
Here is my implementation. Note that I do the dp from [n] back to [n to 1]. Therefore all the right subtree structures are fixed and new values are inserted into the left side, opposite to making BSTs from 1 to [1 to n].
Hi, your solution is not a DP. So there will exist so many duplicate trees created during the recursion, which will waste too much time.
Oh yes. It took me a while to see what you are saying. Subtrees could be reused with the DP approach. Not only it saves time but also space is freed from creating extra nodes of the same value. Although having trees that share branches could be tricky to deal with in the real world, it is the best solution for an algorithm exercise indeed.
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> res = new ArrayList<>();
        res.add(null);
        for(; n > 0; n--) {
            List<TreeNode> next = new ArrayList<>();
            for(TreeNode node: res) {
                //the special case when Node(n) is root of new tree
                TreeNode root = new TreeNode(n); 
                root.right = node;
                next.add(root);
               //while loop inserts new value to every possible position into the left tree side
                while(node != null) {
                    TreeNode cRoot = new TreeNode(root.right.val);
                    //clone left subtree
                    cRoot.left = copyTree(root.right.left);
                    //reusing - point new root.right to the original right subtree
                    cRoot.right = root.right.right;
                    //curr is the cutoff node whose right child will be replaced by the new n 
                    TreeNode curr = getValNode(cRoot, node.val); 
                    //place n as curr's right child, make curr's original right child as the left child of n.
                    TreeNode tmp = curr.left;
                    curr.left = new TreeNode(n);
                    curr.left.right = tmp;

                    next.add(cRoot);
                    node = node.left;
                }
            }
            res = next;
        }
        return res;
    }
    private TreeNode getValNode(TreeNode n, int val) { //find the cutoff node in the new tree
        while(n != null) {
            if(n.val == val) break;
            n = n.left;
        }
        return n;
    }

    private TreeNode copyTree(TreeNode root) { //clone the right subtree
        if(root == null) return null;
        TreeNode cRoot = new TreeNode(root.val);
        cRoot.left = copyTree(root.left);
        cRoot.right = copyTree(root.right);
        return cRoot;
    }


X. DP 2
https://discuss.leetcode.com/topic/3079/a-simple-recursive-solution/10
Using DP causes two problems:
  1. It consumes lots of space, so possible running out of heap space for large n
  2. Using DP means you are reusing Subtree[start, end] solution. Which means if two unique BST both contains Subtree[3, 5], you are using the same saved subtree in two different BST. It is not a completely deep copy.

Noticing the repeat computation in the above algorithm gives us a hint of DP: Can we store some intermediate results so as to reuse it rather than recomputing it?

The answer is yes and we can store BSTs of range [i .. i+k] and then for next range [i .. i+k+1] we can reuse previous results!
  • Create a table T containing lists of BSTs such that T[il] = a list of BSTs of range [i .. i+l].
  • Initialize the table with T[i, 0] which are all single node trees.
  • Increasing the size of range from 1 to n-1 and fill up the table.
    For each range size l,
    •  For each starting value i,
      • For each value k in [ii+l], construct BSTs with root of k, left subtree from BSTs of [ik-i-1] and right subtree from BSTs of [k+1i+l-k-1].
  • Finally, T[0, n-1] gives us the result of all BSTs.
Exponential time: since we recompute BSTs in subrange [i .. j] repeatedly.

This algorithm sacrifice space for time. Since each subtree is only computed and stored once, the time and space complexities are equal to the total number of unique BSTs, which is the Catalan number as proven in previous post.

There are other ways to build such a table. For example, build up a table of T such that T[ij] = a list of BSTs of range [i .. j]. In that case, for each T[ij] where i > j we need to put an empty tree there.
public ArrayList<TreeNode> generateTrees(int n) {  
   if (n < 1) {  
     ArrayList<TreeNode> trees = new ArrayList<TreeNode>();  
     trees.add(null);  
     return trees;  
   }  
   
   // T[i,l] contains a list of BSTs of [i .. i+l]  
   ArrayList<ArrayList<ArrayList<TreeNode>>> allNumTrees = new ArrayList<ArrayList<ArrayList<TreeNode>>>(n);  
   
   // init with single node trees  
   for (int i=1; i<=n; ++i) {  
     ArrayList<ArrayList<TreeNode>> numTrees = new ArrayList<ArrayList<TreeNode>>(n-i);  
     ArrayList<TreeNode> trees = new ArrayList<TreeNode>();  
     TreeNode root = new TreeNode(i);  
     trees.add(root);  
     numTrees.add(trees);  
     allNumTrees.add(numTrees);  
   }  
   
   // fill up the table  
   for (int l=1; l<n; ++l) { // levels  
     for (int i=0; i<n-l; ++i) { // starting number  
       ArrayList<ArrayList<TreeNode>> numTrees = allNumTrees.get(i);  
       ArrayList<TreeNode> trees = new ArrayList<TreeNode>();  
       for (int k=i; k<=i+l; ++k) { // root value  
         if (k == i) {  
           for (TreeNode right : allNumTrees.get(k+1).get(l-1)) {  
             TreeNode root = new TreeNode(k+1);  
             root.right = right;  
             trees.add(root);  
           }  
         } else if (k == i+l) {  
           for (TreeNode left : allNumTrees.get(i).get(l-1)) {  
             TreeNode root = new TreeNode(k+1);  
             root.left = left;  
             trees.add(root);  
           }  
         } else {  
           for (TreeNode left : allNumTrees.get(i).get(k-i-1)) {  
             for (TreeNode right : allNumTrees.get(k+1).get(i+l-k-1)) {  
               TreeNode root = new TreeNode(k+1);  
               root.left = left;  
               root.right = right;  
               trees.add(root);  
             }  
           }  
         }  
       }  
       numTrees.add(trees);  
     }  
   }  
   
   return allNumTrees.get(0).get(n-1);  
 } 

https://leetcode.com/discuss/9790/java-solution-with-dp
result[i] stores the result until length i. For the result for length i+1, select the root node j from 0 to i, combine the result from left side and right side. Note for the right side we have to clone the nodes as the value will be offsetted by j.
Why do we need the clone method, and Why we apply it on the right subtree only!?

This is because for the left nodes, they always start from 1, which have the same values with those in dp[]; While the right nodes, starting at j+1, so they need offset = j+1;
F(i, j) = G(j-1) * G(i-j)
G(n) = F(1, n) + F(2, n) + ... + F(n, n);
G(n) = G(0, n-1) + G(1, n-2) + .. + G(n-1) * G(0)
public static List<TreeNode> generateTrees(int n) { List<TreeNode>[] result = new List[n+1]; result[0] = new ArrayList<TreeNode>(); result[0].add(null); for(int len = 1; len <= n; len++){ result[len] = new ArrayList<TreeNode>(); for(int j=0; j<len; j++){ for(TreeNode nodeL : result[j]){ for(TreeNode nodeR : result[len-j-1]){ TreeNode node = new TreeNode(j+1); node.left = nodeL; node.right = clone(nodeR, j+1); result[len].add(node); } } } } return result[n]; } private static TreeNode clone(TreeNode n, int offset){ if(n == null) return null; TreeNode node = new TreeNode(n.val + offset); node.left = clone(n.left, offset); node.right = clone(n.right, offset); return node; }
Your code is better than mine, but it's not easy to understand why not to clone left, there're some node share,but it doesn't matter,because they are all left node.And it took me some time to understand.
https://leetcode.com/discuss/10254/a-simple-recursive-solution
http://www.programcreek.com/2014/05/leetcode-unique-binary-search-trees-ii-java/
https://leetcode.com/discuss/24305/divide-and-conquer-f-i-g-i-1-g-n-i
public List<TreeNode> generateTrees(int n) {
    return generateTrees(1, n);
}
public List<TreeNode> generateTrees(int start, int end) {
    List<TreeNode> list = new LinkedList<>();
 
    if (start > end) {
        list.add(null);
        return list;
    }
 
    for (int i = start; i <= end; i++) {
        List<TreeNode> lefts = generateTrees(start, i - 1);
        List<TreeNode> rights = generateTrees(i + 1, end);
        for (TreeNode left : lefts) {
            for (TreeNode right : rights) {
                TreeNode node = new TreeNode(i);
                node.left = left;
                node.right = right;
                list.add(node);
            }
        }
    }
 
    return list;
}
http://gongxuns.blogspot.com/2013/01/leetcodeunique-binary-search-trees-ii.html
    public ArrayList<TreeNode> generateTrees(int a, int b){
        ArrayList<TreeNode> res = new ArrayList<TreeNode>();
        
        if(a>b){
            res.add(null);   
        }else if(a==b){//
            res.add(new TreeNode(a));
        }else{
            for(int i=a;i<=b;i++){
                ArrayList<TreeNode> temp1 = generateTrees(a,i-1);
                ArrayList<TreeNode> temp2 = generateTrees(i+1,b);
                
                for(TreeNode n:temp1){
                    for(TreeNode m:temp2){
                        TreeNode temp= new TreeNode(i);
                        temp.left=n;
                        temp.right=m;
                        res.add(temp);
                    }
                }

            }
        } 
        return res;
    }
def generateTrees(self, n):
    def node(val, left, right):
        node = TreeNode(val)
        node.left = left
        node.right = right
        return node
    def trees(first, last):
        return [node(root, left, right)
                for root in range(first, last+1)
                for left in trees(first, root-1)
                for right in trees(root+1, last)] or [None]
    return trees(1, n)
Or even just four lines, if it's not forbidden to add an optional argument:
def node(val, left, right):
    node = TreeNode(val)
    node.left = left
    node.right = right
    return node

class Solution:
    def generateTrees(self, last, first=1):
        return [node(root, left, right)
                for root in range(first, last+1)
                for left in self.generateTrees(root-1, first)
                for right in self.generateTrees(last, root+1)] or [None]
http://www.jiuzhang.com/solutions/unique-binary-search-trees-ii/
https://leetcode.com/discuss/31127/a-simple-bottom-up-dp-solution

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