Monday, February 1, 2016

LeetCode 331 - Verify Preorder Serialization of a Binary Tree


http://bookshadow.com/weblog/2016/02/01/leetcode-verify-preorder-serialization-binary-tree/
One way to serialize a binary tree is to use pre-oder 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 '#' representingnull 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
https://discuss.leetcode.com/topic/35976/7-lines-easy-java-solution
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;
}
generalize the idea to postorder is easy. Just reverse traversal the strings, it is the same.
But the tricky one is inorder. After all inorder is not able to deserialize even if the serialization is correct.
For example, given "#,1,#,2,#"。It can either be a tree rooted with 1 or a tree rooted with 2. Both are valid. Thus I really doubt inorder can verify easily anyhow.
http://www.cnblogs.com/grandyang/p/5174738.html
我们通过举一些正确的例子,比如"9,3,4,#,#,1,#,#,2,#,6,#,#" 或者"9,3,4,#,#,1,#,#,2,#,6,#,#"等等,可以观察出如下两个规律:
1. 数字的个数总是比#号少一个
2. 最后一个一定是#号
那么我们加入先不考虑最后一个#号,那么此时数字和#号的个数应该相同,如果我们初始化一个为0的计数器,遇到数字,计数器加1,遇到#号,计数器减1,那么到最后计数器应该还是0。下面我们再来看两个返回False的例子,"#,7,6,9,#,#,#"和"7,2,#,2,#,#,#,6,#",那么通过这两个反例我们可以看出,如果根节点为空的话,后面不能再有节点,而且不能有三个连续的#号出现。所以我们再加减计数器的时候,如果遇到#号,且此时计数器已经为0了,再减就成负数了,就直接返回False了,因为正确的序列里,任何一个位置i,在[0, i]范围内的#号数都不大于数字的个数的。当循环完成后,我们检测计数器是否为0的同时还要看看最后一个字符是不是#号
https://leetcode.com/discuss/83809/simple-o-n-solution
Use iterative preorder traversal, actually no need to use stack, just a integer to track the depth of the stack.
public boolean isValidSerialization(String preorder) {
    if (preorder == null || preorder.length() == 0) return false;
    String[] strs = preorder.split(",");
    int depth = 0;
    int i = 0;
    while (i < strs.length - 1) {
        if (strs[i++].equals("#")) {
            if (depth == 0) return false;
            else depth--;
        }
        else depth++;
    }
    if (depth != 0) return false;
    return strs[strs.length - 1].equals("#");
}

X. 入度和出度的差
https://www.hrwhisper.me/leetcode-verify-preorder-serialization-of-a-binary-tree/
对于二叉树,我们把空的地方也作为叶子节点(如题目中的#),那么有
  • 所有的非空节点提供2个出度和1个入度(根除外)
  • 所有的空节点但提供0个出度和1个入度
我们在遍历的时候,计算diff = outdegree – indegree. 当一个节点出现的时候,diff – 1,因为它提供一个入度;当节点不是#的时候,diff+2(提供两个出度) 如果序列式合法的,那么遍历过程中diff >=0 且最后结果为0.
https://leetcode.com/discuss/83824/7-lines-easy-java-solution
http://algobox.org/verify-preorder-serialization-of-a-binary-tree/
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 decreasediff by 1, because the node provides an in degree. If the node is not null, we increase diff by2, because it provides two out degrees. If a serialization is correct, diff should never be negative and diff will be zero when finished.

If diff is never negative and is zero when finished, the serialization is correct.
Let's assume

If a serialization is correct, diff should never be negative and diff will be zero when finished
is sounded, how do we argue the opposite is also true, 
i.e.,if diff never becomes negative and diff is zero at the end, then the serialization is correct

That is, we know a -> b is true, but it does not necessarily mean b -> a is also true. The method I used also has this kind of unresolved question (if we are strict to ourselves) and I cannot explain it well yet.
 this solution could solve preorder and postorder but inorder, just do some modify on '''if (--diff < 0) return false;‘’‘
in-order will be quite easy. the sequence will be 01010101010101...

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;
}

If we treat null's as leaves, then the binary tree will always be full. A full binary tree has a good property that # of leaves = # of nonleaves + 1. Since we are given a pre-order serialization, we just need to find the shortest prefix of the serialization sequence satisfying the property above. If such prefix does not exist, then the serialization is definitely invalid; otherwise, the serialization is valid if and only if the prefix is the entire sequence.
// Java Code
public boolean isValidSerialization(String preorder) {
    int nonleaves = 0, leaves = 0, i = 0;
    String[] nodes = preorder.split(",");
    for (i=0; i<nodes.length && nonleaves + 1 != leaves; i++)
        if (nodes[i].equals("#")) leaves++;
        else nonleaves++;
    return nonleaves + 1 == leaves && i == nodes.length;
}
Similar idea but a different way of thinking (use dangling edges):
public boolean isValidSerialization(String preorder) {
    String[] nodes = preorder.split(",");
    int n = nodes.length;
    int numOfDanglingEdge = 1;
    for (int i = 0; i < n; ++i) {
        if (nodes[i].equals("#")) {
            numOfDanglingEdge--;
            // if nodes are exhausted, found a match
            // o.w. return false, as there is no dangling edge to place node i+1
            if (numOfDanglingEdge == 0) {
                return i == n-1;
            }
        } else {
            numOfDanglingEdge++;
        }
    }
    // there are dangling edges left
    return false;
}
Verification of postorder is answered by @ j0ames.wang.ccc and @dietpepsi. For inorder, a valid serialization has to be of the form #x#x#x#. Because we known # of leaves = # of internal node + 1, and in a valid inorder serialization, no two # can be adjacent to each other (any adjacent pair in an inorder traversal would have to have one internal node). Therefore, to verify a valid inorder serialization, we just need to check if the serialization is of the form#x#x#x#. But as @dietpepsi pointed out already, it won't be uniquely deserialized, it can generate k trees, where k is catalan number.
X.
https://leetcode.com/discuss/83809/simple-o-n-solution
Use iterative preorder traversal, actually no need to use stack, just a integer to track the depth of the stack.
public class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder == null || preorder.length() == 0) return false;
        String[] strs = preorder.split(",");
        int depth = 0;
        int i = 0; 
        while (i < strs.length - 1) {
            if (strs[i++].equals("#")) {
                if (depth == 0) return false;
                else depth--;
            }
            else depth++;
        }
        if (depth != 0) return false;
        return strs[strs.length - 1].equals("#");
    }
}
public boolean isValidSerialization(String preorder) {
    String[] strs = preorder.split(",");
    int N = strs.length, count = 0, i = -1;
    while(++i<N-1) {
        if(!"#".equals(strs[i])) ++count;
        else if(--count<0) return false;
    }
    return count==0 && "#".equals(strs[i]);
}
Interesting fact:
  • number of sentinel nodes = number of non-sentinel nodes + 1
Key idea:
  • count: counter of non-sentinel nodes - sentinel nodes up to index i. So we increase counter if current value is not # (it is like push item into stack), otherwise decrease it (it is like pop item out of stack)
  • if current value is # and counter is already 0, return false (it is like the case when stack is already empty and you cannot pop anymore)
  • however, if counter is 0 and we already moved to the last location, return true because of the above interesting fact
public boolean isValidSerialization(String preorder) { int need = 1; for (String val : preorder.split(",")) { if (need == 0) return false; need -= " #".indexOf(val); } return need == 0; }
X. Use Regex
Yep, only O(n^2), and that example is equivalent to the one I also gave andrei3 :-). I thought about using "(\\d+,#,)+#" which would solve it quickly, but it would still be slow for "always only left child" and I'm guessing also for lots of less simple cases, so I gave up trying to make it fast and just went for making it simple.
public boolean isValidSerialization(String preorder) { String s = preorder.replaceAll("\\d+,#,#", "#"); return s.equals("#") || !s.equals(preorder) && isValidSerialization(s); }
https://leetcode.com/discuss/83896/8-line-regex-solution-without-building-the-tree
public bool IsValidSerialization(string preorder) {
    var t = String.Empty;
    preorder = Regex.Replace(preorder, "[0-9]+", "0");
    while (preorder != t)
    {
        t = preorder;
        preorder = preorder.Replace("0,#,#", "#");
    }
    return preorder == "#";
}
X. Recursive Version
The idea is that if current is ‘#’, we simply return true. If current is a number, call validHelper 2 times with pos++. In the end, return true if pos == list.length – 1.
public static boolean isValidSerialization(String preorder) {
    String[] list = preorder.split(",");
    int[] pos = new int[] {-1};
    if (!validHelper(list, pos) || pos[0] != list.length - 1) { // in the end, pos[0] should equal len - 1
        return false;
    }
    return true;
}

public static boolean validHelper(String[] list, int[] pos) {
    pos[0]++;
    if (pos[0] >= list.length) {  // add pos[0] first
        return false;
    }
    if (list[pos[0]].equals("#")) { // if is '#', return true.
        return true;
    }
    // if is a number, call 2 times.
    return validHelper(list, pos) && validHelper(list, pos);
}
X. 利用栈(Stack)数据结构
https://discuss.leetcode.com/topic/35973/java-intuitive-22ms-solution-with-stack
public boolean isValidSerialization(String preorder) { // using a stack, scan left to right // case 1: we see a number, just push it to the stack // case 2: we see #, check if the top of stack is also # // if so, pop #, pop the number in a while loop, until top of stack is not # // if not, push it to stack // in the end, check if stack size is 1, and stack top is # if (preorder == null) { return false; } Stack<String> st = new Stack<>(); String[] strs = preorder.split(","); for (int pos = 0; pos < strs.length; pos++) { String curr = strs[pos]; while (curr.equals("#") && !st.isEmpty() && st.peek().equals(curr)) { st.pop(); if (st.isEmpty()) { return false; } st.pop(); } st.push(curr); } return st.size() == 1 && st.peek().equals("#"); }
http://www.programcreek.com/2015/01/leetcode-verify-preorder-serialization-of-a-binary-tree-java/
public boolean isValidSerialization(String preorder) {
    LinkedList<String> stack = new LinkedList<String>();
    String[] arr = preorder.split(",");
 
    for(int i=0; i<arr.length; i++){
        stack.add(arr[i]);
 
        while(stack.size()>=3 
            && stack.get(stack.size()-1).equals("#")
            && stack.get(stack.size()-2).equals("#")
            && !stack.get(stack.size()-3).equals("#")){
 
            stack.remove(stack.size()-1);
            stack.remove(stack.size()-1);
            stack.remove(stack.size()-1);
 
            stack.add("#");
        }
 
    }
 
    if(stack.size()==1 && stack.get(0).equals("#"))
        return true;
    else
        return false;
}
http://blog.csdn.net/yeqiuzs/article/details/51527069
两个#可以退一个栈,最后如果栈只剩一个#则true否则false
  1. public boolean isValidSerialization(String preorder) {    
  2.     Stack<String> stack = new Stack<String>();    
  3.     String ps[] = preorder.split(",");    
  4.     for (int i = 0; i < ps.length; i++) {    
  5.         stack.push(ps[i]);    
  6.         while (!stack.isEmpty() && stack.peek().equals("#") && stack.size() >= 3    
  7.                 && stack.get(stack.size() - 2).equals("#") && !stack.get(stack.size() - 3).equals("#")) {    
  8.             stack.pop();    
  9.             stack.pop();    
  10.             stack.pop();    
  11.             stack.push("#");    
  12.         }    
  13.     }    
  14.     return stack.size() == 1 && stack.peek().equals("#");    
  15. }  
将元素压入栈
如果当前栈的深度≥3,并且最顶端两个元素为'#', '#',而第三个元素不为'#',则将这三个元素弹出栈顶,然后向栈中压入一个'#',重复此过程
最后判断栈中剩余元素是否只有一个'#'
def isValidSerialization(self, preorder): stack = collections.deque() for item in preorder.split(','): stack.append(item) while len(stack) >= 3 and \ stack[-1] == stack[-2] == '#' and \ stack[-3] != '#': stack.pop(), stack.pop(), stack.pop() stack.append('#') return len(stack) == 1 and stack[0] == '#'
http://www.voidcn.com/blog/sun_wangdong/article/p-5025350.html
http://www.programcreek.com/2015/01/leetcode-verify-preorder-serialization-of-a-binary-tree-java/
已例子一为例:”9,3,4,#,#,1,#,#,2,#,6,#,#” 遇到x # #的时候,就把它变为 #
我模拟一遍过程:
  1. 9,3,4,#,# => 9,3,# 继续读
  2. 9,3,#,1,#,# => 9,3,#,# => 9,# 继续读
  3. 9,#2,#,6,#,# => 9,#,2,#,# => 9,#,# => #
从以上步骤可以得到规律,也就是二叉树先序遍历的过程,此题按照倒退,可以发现如果出现的连续两个"#",那么可以和之前的那个非"#"的数字合并为一个"#",其实也就是考虑将一个节点的合并为它的父节点的左子树或者是右子树。
用堆栈来做,其中堆栈的头顶的元素可以用stack.get(stack.size() - 1)来得到,并且判断stack中的元素和某一个元素是否相等的方法不能用"==",而必须用equals来做。
public boolean isValidSerialization(String preorder)
{
  Stack<String> stack = new Stack<String>();
  String[] num = preorder.split(",");
  for(int i = 0; i < num.length; i++)
  {
   stack.push(num[i]);
   while(stack.size() >= 3)
   {
    //这里必须要使用equals,如果用==就会报错
    if(stack.get(stack.size() - 1).equals("#") && stack.get(stack.size() - 2).equals("#") && !stack.get(stack.size() - 3).equals("#"))
    {
     stack.pop();
     stack.pop();
     stack.pop();
     stack.push("#");
    }
    else 
     break;
   }
  }
  //注意一种特殊的情况,如果是只有一个"#",那么返回的是true,而不是false。
  return stack.size() == 1 && stack.peek().equals("#");
 }
此外,还需要注意一种特殊情况,也就是只有一个"#"的情况,此表示没有节点,那么返回的是true,而不是false.
另附递归重建树的解法(Time Limit Exceeded),详见代码。
def isValidSerialization(self, preorder): items = preorder.split(',') map = dict() def isValid(start, end): size = end - start + 1 if size == 0: return False if items[start] == '#': return size == 1 if size == 3: return items[start + 1] == items[start + 2] == '#' for k in range(2, size): left, right = (start + 1, start + k - 1), (start + k, end) vl = map.get(left) if vl is None: vl = map[left] = isValid(*left) vr = map.get(right) if vr is None: vr = map[right] = isValid(*right) if vl and vr: return True return False return isValid(0, len(items) - 1)

http://www.jiuzhang.com/solutions/verify-preorder-serialization-of-a-binary-tree/
    public boolean isValidSerialization(String preorder) {
        String s = preorder;
        boolean flag = true;
        while (s.length() > 1) {
            int index = s.indexOf(",#,#");
            if (index < 0) {
                flag = false;
                break;
            }
            int start = index;
            while (start > 0 && s.charAt(start - 1) != ',')
            {
                start --;
            }
            if (s.charAt(start) == '#') {
                flag = false;
                break;
            }
            s = s.substring(0, start) + s.substring(index + 3);
        }
        if (s.equals("#") && flag) 
            return true;
        else 
            return false;
    }

public boolean isValidSerialization_PostOrder(String postorder) { String[] nodes = postorder.split(","); int diff = 1; for (String node : nodes) { diff--; if (!node.equals("#")) diff += 2; // Post-Order traversal fail criteria if (diff > 0) return false; } return diff == 0; }

X. Recursion version
http://www.allenlipeng47.com/blog/index.php/2016/02/01/verify-preorder-serialization-of-a-binary-tree/
The idea is that if current is ‘#’, we simply return true. If current is a number, call validHelper 2 times with pos++. In the end, return true if pos == list.length – 1.
public static boolean isValidSerialization(String preorder) {
    String[] list = preorder.split(",");
    int[] pos = new int[] {-1};
    if (!validHelper(list, pos) || pos[0] != list.length - 1) { // in the end, pos[0] should equal len - 1
        return false;
    }
    return true;
}

public static boolean validHelper(String[] list, int[] pos) {
    pos[0]++;
    if (pos[0] >= list.length) {  // add pos[0] first
        return false;
    }
    if (list[pos[0]].equals("#")) { // if is '#', return true. // and no more elements?
        return true;
    }
    // if is a number, call 2 times.
    return validHelper(list, pos) && validHelper(list, pos);
}



No comments:

Post a Comment

Labels

GeeksforGeeks (1107) LeetCode (993) Algorithm (795) Review (766) to-do (633) LeetCode - Review (514) Classic Algorithm (324) Dynamic Programming (293) Classic Interview (288) Google Interview (242) Tree (145) POJ (139) Difficult Algorithm (132) LeetCode - Phone (127) EPI (125) Different Solutions (120) Bit Algorithms (118) Lintcode (113) Cracking Coding Interview (110) Smart Algorithm (109) Math (107) HackerRank (89) Binary Tree (82) Binary Search (81) Graph Algorithm (74) Greedy Algorithm (72) DFS (67) LeetCode - Extended (62) Interview Corner (61) Stack (60) List (58) Advanced Data Structure (56) BFS (54) Codility (54) ComProGuide (52) Algorithm Interview (50) Geometry Algorithm (48) Binary Search Tree (46) USACO (46) Trie (45) Mathematical Algorithm (42) ACM-ICPC (41) Interval (41) Data Structure (40) Knapsack (40) Space Optimization (40) Jobdu (39) LeetCode Hard (39) Recursive Algorithm (39) Matrix (38) String Algorithm (38) Backtracking (36) Codeforces (36) Introduction to Algorithms (36) Must Known (36) Beauty of Programming (35) Sort (35) Union-Find (34) Array (33) prismoskills (33) Segment Tree (32) Sliding Window (32) Data Structure Design (31) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Company-Airbnb (29) Company-Zenefits (28) Microsoft 100 - July (28) Palindrome (28) to-do-must (28) Priority Queue (27) Random (27) Graph (26) Company - LinkedIn (25) GeeksQuiz (25) Logic Thinking (25) Pre-Sort (25) hihocoder (25) Queue (24) Company-Facebook (23) High Frequency (23) Post-Order Traverse (23) TopCoder (23) Algorithm Game (22) Bisection Method (22) Hash (22) Binary Indexed Trees (21) DFS + Review (21) Lintcode - Review (21) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Merge Sort (20) O(N) (20) Follow Up (19) Time Complexity (19) Two Pointers (19) UVA (19) Ordered Stack (18) Probabilities (18) Company-Uber (17) Game Theory (17) Topological Sort (17) Codercareer (16) Heap (16) Shortest Path (16) String Search (16) Tree Traversal (16) itint5 (16) Difficult (15) Iterator (15) BST (14) Number (14) Number Theory (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Euclidean GCD (13) KMP (13) Long Increasing Sequence(LIS) (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) LeetCode - Classic (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) Reverse Thinking (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Miscs (11) Princeton (11) Proof (11) Tree DP (11) X Sum (11) 挑战程序设计竞赛 (11) Bisection (10) Bucket Sort (10) Coin Change (10) Company - Microsoft (10) DFS+Cache (10) Facebook Hacker Cup (10) HackerRank Easy (10) O(1) Space (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) DP-Multiple Relation (9) DP-Space Optimization (9) Divide and Conquer (9) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Prefix Sum (9) Quick Sort (9) Simulation (9) Stack Overflow (9) Stock (9) System Design (9) TreeMap (9) Use XOR (9) Book Notes (8) Bottom-Up (8) Company-Amazon (8) DFS+BFS (8) LeetCode - DP (8) Left and Right Array (8) Linked List (8) Longest Common Subsequence(LCS) (8) Prime (8) Suffix Tree (8) Tech-Queries (8) Traversal Once (8) 穷竭搜索 (8) Algorithm Problem List (7) Expression (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Inversion (7) Kadane’s Algorithm (7) Level Order Traversal (7) Math-Divisible (7) Probability DP (7) Quick Select (7) Radix Sort (7) n00tc0d3r (7) 蓝桥杯 (7) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) DP-Print Solution (6) Dijkstra (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Manacher (6) Minimum Spanning Tree (6) Morris Traversal (6) Multiple Data Structures (6) One Pass (6) Programming Pearls (6) Pruning (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Stream (6) Suffix Array (6) Threaded (6) TreeSet (6) Xpost (6) reddit (6) AI (5) Algorithm - Brain Teaser (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) Cycle (5) DP-Include vs Exclude (5) Fast Slow Pointers (5) Find Rule (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) Matrix Chain Multiplication (5) Maze (5) Microsoft Interview (5) Pre-Sum (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sudoku (5) Sweep Line (5) Word Search (5) jiuzhang (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Abbreviation (4) Anagram (4) Anagrams (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Consistent Hash (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) LeetCode - Recursive (4) LeetCode - TODO (4) MST (4) MinMax (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Probability (4) Programcreek (4) Spell Checker (4) Stock Maximize (4) Subset Sum (4) Subsets (4) Symbol Table (4) Triangle (4) Water Jug (4) algnotes (4) fgdsb (4) to-do-2 (4) 最大化最小值 (4) A Star (3) Algorithm - How To (3) Algorithm Design (3) B Tree (3) Big Data Algorithm (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) Finite Automata (3) Github (3) GoLang (3) Graph - Bipartite (3) Include vs Exclude (3) Joseph (3) Jump Game (3) K (3) Knapsack-多重背包 (3) LeetCode - Bit (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) O(N) Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Shuffle (3) Sieve of Eratosthenes (3) Stack - Smart (3) State Machine (3) Subtree (3) Transform Tree (3) Trie + DFS (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Ladder (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) Binary Search - Smart (2) Binomial Coefficient (2) Bit Counting (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) Company-Snapchat (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) Edit Distance (2) Factor (2) Forward && Backward Scan (2) GoHired (2) Graham Scan (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) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) Math-Remainder Queue (2) Matrix Power (2) Median (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Parent-Only Tree (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Regular Expression (2) Return Multiple Values (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Tree Without Tree Predefined (2) Word Break (2) Word Graph (2) Word Trie (2) Yahoo Interview (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Augmented BST (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 Sarch Tree (1) Binary String (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) Cloest (1) Clone (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-Yelp (1) Compression Algorithm (1) Concurrency (1) Cont Improvement (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) Diagonal (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 - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Knuth Shuffle (1) Kosaraju’s algorithm (1) Kruskal (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (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) Machine Learning (1) Maintain State (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) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-End BFS (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Element (1) Next Successor (1) Offline Algorithm (1) PAT (1) Parenthesis (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) PreProcess (1) Probabilistic Data Structure (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) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) Square (1) Streaming Algorithm (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) Test Cases (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 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) Virtual Matrix (1) Wiggle Sort (1) Wikipedia (1) ZOJ (1) ZigZag (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