Tuesday, April 24, 2018

LeetCode 790 - Domino and Tromino Tiling


https://leetcode.com/problems/domino-and-tromino-tiling/description/
We have two types of tiles: a 2x1 domino shape, and an "L" tromino shape. These shapes may be rotated.
XX  <- domino

XX  <- "L" tromino
X
Given N, how many ways are there to tile a 2 x N board? Return your answer modulo 10^9 + 7.
(In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.)
Example:
Input: 3
Output: 5
Explanation: 
The five different ways are listed below, different letters indicates different tiles:
XYZ XXZ XYY XXY XYY
XYZ YYZ XZZ XYY XXY
Note:
  • N  will be in range [1, 1000].
https://leetcode.com/problems/domino-and-tromino-tiling/discuss/116664/Schematic-explanation-of-two-equivalent-DP-recurrence-formula
First, how many types of tiles do we have (including rotation)?
The answer is six: two types from domino and four types from trimino. I label them as follows:
type 1: imagerepresenting vertical domino
type 2: imagerepresenting horizontal domino
type 3: imagerepresenting L-shaped trimino
type 4: imagerepresenting Gamma-shaped trimino
type 5: image representing mirrored-L-shaped trimino
type 6: imagerepresenting mirrored-Gamma-shaped trimino
Now let's define T(N) as the number of ways tiling the 2 x N board. To obtain the recurrence relations for T(N), we shall consider the very last tile in the 2 x Nboard (this is the tile which occupies at least one of the two grids at index N and completes the 2 x N board). So what type can it be?
Immediately we can rule out type 3 and 4, because they will never complete the board, thus cannot be the last tile. So we end up with four choices for the last tile:
  1. The last tile is of type 1: in this case, the rest tiles will fill up the 2 x (N-1) board, then by definition, the number of ways for this case will be T(N-1).
  2. The last tile is of type 2: in this case, the second to last tile must also be of type 2 (so they together fill up the last 2 x 2 region), and the rest tiles will fill up the 2 x (N-2) board, again by definition, the number of ways for this case will be T(N-2).
  3. The last tile is of type 5: in this case, the rest tiles must fill up the 2 x (N-1) board except for the lower grid at index N-1, like this shape: image. Our definition of T(N) does not cover this case, so we have to generalize it and define T_up(N) as the the number of ways to fill a 2 x N board except for the last lower grid. Then the number of ways for this case will be T_up(N-1).
  4. The last tile is of type 6: in this case, the rest tiles must fill up the 2 x (N-1) board except for the upper grid at index N-1, like this shape: image. Our definition of T(N) does not cover this case either, so we define T_down(N) as the the number of ways to fill a 2 x N board except for the last upper grid. Then the number of ways for this case will be T_down(N-1).
It's easy to show that the four cases will not overlap with each other (because at least the last tile will be different), and since the last tile must be one of the four cases, we conclude:
T(N) = T(N-1) + T(N-2) + T_up(N-1) + T_down(N-1)
This looks like a recurrence formula, except that we do not know T_up(N) and T_down(N) yet. To figure them out, we can follow exactly the same analyses above by considering the very last tile for each of them.
Take T_up(N) as an example. We want to fill up a board shape like this: image. What could the type of the very last tile be? The answer is: type 2(horizontal domino) and type 4 (Gamma-shaped trimino). For the former, the rest of tiles will fill up a 2 x (N-1) board except for the last upper grid, and by definition, there are T_down(N-1) ways to do this. For the latter, the rest tiles will fill up a 2 x (N-2) board completely, and by definition, there are T(N-2) ways to do so. So we conclude:
T_up(N) = T_down(N-1) + T(N-2)
Similarly we can obtain:
T_down(N) = T_up(N-1) + T(N-2)
And, there you go, we have found the recurrence relations for T(N)T_up(N)T_down(N):
T(N) = T(N-1) + T(N-2) + T_up(N-1) + T_down(N-1)
T_up(N) = T_down(N-1) + T(N-2)
T_down(N) = T_up(N-1) + T(N-2)
The termination conditions are as follows:
For N = 0, we have T(0) = 1T_up(0) = T_down(0) = 0;
For N = 1, we have T(1) = 1T_up(1) = T_down(1) = 0.
Now it is straightforward to write the O(N) space solution. However, if you notice that T(N)T_up(N)T_down(N) are only related to those at indices N-1 and N-2, the space can be cut to O(1). Here is a quick implementation in Java:
private static final int MOD = 1_000_000_007;
    
public int numTilings(int N) {
    int T_prepre = 1, T_pre = 1;
    int T_up_pre = 0, T_down_pre = 0;
        
    for (int n = 2; n <= N; n++) {
        int T_cur = (int)((0L + T_prepre + T_pre + T_up_pre + T_down_pre) % MOD);
        int T_up_cur = (T_prepre + T_down_pre) % MOD;
        int T_down_cur = (T_prepre + T_up_pre) % MOD;
            
        T_prepre = T_pre;
        T_pre = T_cur;
            
        T_up_pre = T_up_cur;
        T_down_pre = T_down_cur;
    }
        
    return T_pre;
}

Wait..., we are not done yet. It turns out that the recurrence relations for T(N)T_up(N)T_down(N) can be combined into one. To see how, first note that we have:
T(N) = T(N-1) + T(N-2) + T_up(N-1) + T_down(N-1)
T_up(N-1) = T_down(N-2) + T(N-3)
T_down(N-1) = T_up(N-2) + T(N-3)
Now plug the second and third equations into the first one, we get:
T(N) = T(N-1) + T(N-2) + T_down(N-2) + T(N-3) + T_up(N-2) + T(N-3)
which can be regrouped as:
T(N) = T(N-1) + T(N-3) + [T(N-2) + T(N-3) + T_up(N-2) + T_down(N-2)]
Now if you recognize the part in square brakets which is simply T(N-1), we arrive at:
T(N) = 2 * T(N-1) + T(N-3).
I would refer you to this post shared by zhengkaiwei for more explanations of the meaning of this formula. Anyway, the following is the O(N) time and O(1) space based on this formula, where I used p3p2p1 to denote T(N-3)T(N-2)T(N-1) respectively, and initialize them to -10 and 1 to account for correct recurrence values.
private static final int MOD = 1_000_000_007;
    
public int numTilings(int N) {
    int p3 = -1, p2 = 0, p1 = 1;
        
    for (int n = 1; n <= N; n++) {
        int cur = (int)((p1 * 2L + p3) % MOD);
        p3 = p2;
        p2 = p1;
        p1 = cur;
    }
        
    return p1;
}

http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-790-domino-and-tromino-tiling/
dp[i][0]: ways to cover i cols, both rows of i-th col are covered
dp[i][1]:  ways to cover i cols, only top row of i-th col is covered
dp[i][2]:  ways to cover i cols, only bottom row of i-th col is covered
Solution 1: DP
Time complexity: O(N)
Space complexity: O(N)
  int numTilings(int N) {
    constexpr int kMod = 1000000007;
    vector<vector<long>> dp(N + 1, vector<long>(3, 0));    
    dp[0][0] = dp[1][0] = 1;
    for (int i = 2; i <= N; ++i) {
      dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + dp[i - 1][1] + dp[i - 1][2]) % kMod;
      dp[i][1] = (dp[i - 2][0] + dp[i - 1][2]) % kMod;
      dp[i][2] = (dp[i - 2][0] + dp[i - 1][1]) % kMod;
    }
    
    return dp[N][0];
  }

Since dp[i][1] always equals to dp[i][2], we can simplify a bit.
  int numTilings(int N) {
    constexpr int kMod = 1000000007;
    vector<vector<long>> dp(N + 1, vector<long>(2, 0));    
    dp[0][0] = dp[1][0] = 1;
    for (int i = 2; i <= N; ++i) {
      dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + 2 * dp[i - 1][1]) % kMod;
      dp[i][1] = (dp[i - 2][0] + dp[i - 1][1]) % kMod;      
    }
    
    return dp[N][0];
  }
http://www.cnblogs.com/pk28/p/8470177.html
思路:分3个状态,第i列上边凸出,下边凸出,和平的。如图,那么状态转换如图中公式。
https://blog.csdn.net/Faldict/article/details/79392996
It is not difficult to think of dynamic programming after reading the problem. However, the design of the recurrent formula is the key points. Initially, we set dp[0] = dp[1] = 1 and dp[2] = 2 for convenience. When n > 3, we cover the tiles square by square. There are three cases:
  1. Add an “XX” tile vertically and step one square forward.
  2. Add two “XX” tile horizontally and step two square forward.
  3. Add a combination of two trominos and X - 3 dominos and step X square forward.
Thus we get a recurrent formula:
dp[n] = dp[n-1] + dp[n-2] + 2 * \sum_{i=0}^{n-3} dp[i]
  • 1
To speed up the calculation, we use an array to store the data. Notice that the answer should modulo 1e9+7. 
int numTilings(int N) { int md = 1e9+7; long long tiles[1005]; tiles[0] = 1; tiles[1] = 1; tiles[2] = 2; for (int i=3; i <= N; i++) { tiles[i] = tiles[i-1] + tiles[i-2]; for (int j=0; j <= i-3; j++) { tiles[i] += 2 * tiles[j]; tiles[i] %= md; } } return tiles[N]; }


And the formula can be simplified into the form as below, and the proof is omitted:
dp[n] = 2 * dp[n-1] + dp[n-3]
https://leetcode.com/problems/domino-and-tromino-tiling/discuss/116581/Detail-and-explanation-of-O(n)-solution-why-dpn2*dn-1+dpn-3
dp[n]=dp[n-1]+dp[n-2]+ 2*(dp[n-3]+...+d[0])
=dp[n-1]+dp[n-2]+dp[n-3]+dp[n-3]+2*(dp[n-4]+...+d[0])
=dp[n-1]+dp[n-3]+(dp[n-2]+dp[n-3]+2*(dp[n-4]+...+d[0]))
=dp[n-1]+dp[n-3]+dp[n-1]
=2*dp[n-1]+dp[n-3]
 int numTilings(int N) {
    int md=1e9;
    md+=7;
    vector<long long> v(1001,0);
    v[1]=1;
    v[2]=2;
    v[3]=5;
    if(N<=3)
        return v[N];
    for(int i=4;i<=N;++i){
        v[i]=2*v[i-1]+v[i-3]; 
        v[i]%=md;
    }
    return v[N];
    
}

http://bookshadow.com/weblog/2018/02/25/leetcode-domino-and-tromino-tiling/
dp[x][y]表示长度(两行的最小值)为x,末尾形状为y的拼接方法个数
y有三种可能:
0表示末尾没有多余部分

1表示第一行多出1个单元格

2表示第二行多出1个单元格
状态转移方程:
dp[x][0] = (dp[x - 1][0] + sum(dp[x - 2])) % MOD   1个竖条, 2个横条,L7, rotate(L7)

dp[x][1] = (dp[x - 1][0] + dp[x - 1][2]) % MOD    rotate(L),L + 第一行横条

dp[x][2] = (dp[x - 1][0] + dp[x - 1][1]) % MOD    L,rotate(L) + 第二行横条
def numTilings(self, N): """ :type N: int :rtype: int """ MOD = 10**9 + 7 dp = [[0] * 3 for x in range(N + 10)] dp[0] = [1, 0, 0] dp[1] = [1, 1, 1] for x in range(2, N + 1): dp[x][0] = (dp[x - 1][0] + sum(dp[x - 2])) % MOD dp[x][1] = (dp[x - 1][0] + dp[x - 1][2]) % MOD dp[x][2] = (dp[x - 1][0] + dp[x - 1][1]) % MOD return dp[N][0]
Another way to think about this problem
define: dp[i] ways to completely covert the i*2 board.
  int numTilings(int N) {
    constexpr int kMod = 1000000007;
    vector<long> dp(N + 1, 1);
    dp[2] = 2;
    for (int i = 3; i <= N; ++i)
      dp[i] = (dp[i - 3] + dp[i - 1] * 2) % kMod;
    return dp[N];
  }

https://leetcode.com/problems/domino-and-tromino-tiling/discuss/116622/O(logN)-time-O(1)-space-linear-algebraic-algorithm-(in-python)

No comments:

Post a Comment

Labels

LeetCode (1200) GeeksforGeeks (1127) Review (893) Algorithm (795) LeetCode - Review (649) to-do (639) Dynamic Programming (329) Classic Algorithm (323) Classic Interview (288) Google Interview (245) Tree (145) POJ (140) Difficult Algorithm (131) LeetCode - Phone (127) EPI (125) Bit Algorithms (121) Different Solutions (120) Lintcode (112) Cracking Coding Interview (110) Math (109) Smart Algorithm (109) HackerRank (89) Binary Search (84) Binary Tree (82) Greedy Algorithm (80) Graph Algorithm (76) DFS (73) Stack (68) LeetCode - Extended (62) Interview Corner (61) List (58) BFS (57) Advanced Data Structure (56) Codility (54) ComProGuide (52) LeetCode Hard (52) Algorithm Interview (50) Geometry Algorithm (50) Trie (49) Binary Search Tree (48) Interval (46) USACO (46) Mathematical Algorithm (42) ACM-ICPC (41) Segment Tree (41) Union-Find (41) Data Structure (40) Knapsack (40) Matrix (40) Space Optimization (40) Jobdu (39) Recursive Algorithm (39) Backtracking (38) String Algorithm (38) TopCoder (38) Codeforces (36) Introduction to Algorithms (36) Must Known (36) Beauty of Programming (35) Sort (35) Data Structure Design (34) Sliding Window (34) Array (33) prismoskills (33) Priority Queue (32) HDU (31) Google Code Jam (30) LeetCode - DP (30) Permutation (30) Puzzles (30) Array O(N) (29) Company-Airbnb (29) Company-Zenefits (28) Graph (28) Microsoft 100 - July (28) Palindrome (28) to-do-must (28) Random (27) Queue (26) Binary Indexed Trees (25) Company - LinkedIn (25) GeeksQuiz (25) Logic Thinking (25) Post-Order Traverse (25) Pre-Sort (25) Time Complexity (25) hihocoder (25) Company-Facebook (23) High Frequency (23) Two Pointers (23) Algorithm Game (22) Bisection Method (22) Hash (22) DFS + Review (21) Follow Up (21) Lintcode - Review (21) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Merge Sort (20) O(N) (20) Ordered Stack (20) Topological Sort (19) UVA (19) Company-Uber (17) Game Theory (17) Probabilities (17) Codercareer (16) Heap (16) Iterator (16) Shortest Path (16) String Search (16) Tree Traversal (16) itint5 (16) Difficult (15) BST (14) DP - Tree (14) KMP (14) LeetCode - DFS (14) Number (14) Number Theory (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Euclidean GCD (13) LeetCode - Classic (13) Long Increasing Sequence(LIS) (13) Majority (13) Reverse Thinking (13) mitbbs (13) Algorithm - How To (12) Bisection (12) Combination (12) Computational Geometry (12) Modify Tree (12) Proof (12) Reconstruct Tree (12) Reservoir Sampling (12) TreeMap (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) Miscs (11) O(1) Space (11) Prefix Sum (11) Princeton (11) Rolling Hash (11) X Sum (11) 挑战程序设计竞赛 (11) Bucket Sort (10) Coin Change (10) Company - Microsoft (10) DFS+Cache (10) DP - Bit Masking (10) DP - Digit (10) DP - Interval (10) DP-Space Optimization (10) Divide and Conquer (10) Facebook Hacker Cup (10) HackerRank Easy (10) Kadane - Extended (10) MinMax (10) SPOJ (10) Simulation (10) Theory (10) Tutorialhorizon (10) DP - Probability (9) DP-Multiple Relation (9) Mathblog (9) Max-Min Flow (9) Quick Sort (9) Stack Overflow (9) Stock (9) System Design (9) Use XOR (9) Book Notes (8) Bottom-Up (8) Company-Amazon (8) DFS+BFS (8) Interval Tree (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) TreeSet (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) Inversion (7) Kadane’s Algorithm (7) LeetCode - TODO (7) Level Order Traversal (7) Math-Divisible (7) Quick Select (7) Radix Sort (7) Tree DP (7) n00tc0d3r (7) 蓝桥杯 (7) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (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) Sweep Line (6) Threaded (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 - Knapsack (5) DP-Include vs Exclude (5) Fast Slow Pointers (5) Find Rule (5) Flood fill (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LeetCode - Thinking (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) Word Search (5) jiuzhang (5) 单调栈 (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) Dequeue (4) Distributed (4) Eulerian Cycle (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) LeetCode - Recursive (4) MST (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) 树形DP (4) A Star (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) 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) Parser (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Shuffle (3) Sieve of Eratosthenes (3) Skyline (3) Stack - Smart (3) State Machine (3) Strongly Connected Components (3) Subtree (3) TSP (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 - Trie (2) DP-3D Table (2) DP-Classical (2) DP-Output Solution (2) DP-Slide Window Gap (2) DP-i-k-j (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) Hard (2) Hard Algorithm (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) Monotone Queue (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) 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) Sparse Table (2) Spatial Index (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) ? (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) BFS Hard (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) Clean Code (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) Concise (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) DI (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) DP-树形 (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) 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 - Construction (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode -P (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 Exponentiation (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) 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) Optimal Play (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) Probability DP (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) Revi (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) 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) Two-End-BFS (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