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
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://leetcode.com/discuss/83819/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("#"); }

将元素压入栈
如果当前栈的深度≥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; }



No comments:

Post a Comment

Labels

GeeksforGeeks (959) Algorithm (811) LeetCode (637) to-do (598) Review (340) Classic Algorithm (334) Classic Interview (299) Dynamic Programming (263) Google Interview (234) LeetCode - Review (229) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (118) 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) List (58) Binary Tree (56) 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) Interval (38) Jobdu (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) Array (33) Trie (33) prismoskills (33) Segment Tree (32) Space Optimization (32) Union-Find (32) Backtracking (31) 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 (26) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Queue (22) DFS + Review (21) Hash (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) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Bisection Method (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) 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) Divide and Conquer (8) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (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) Suffix Tree (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) 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) Kadane’s Algorithm (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) 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