Monday, April 17, 2017

LeetCode 546 - Remove Boxes


Related: Box Stacking Problem
https://leetcode.com/problems/remove-boxes
Given several boxes with different colors represented by different positive numbers.
You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (composed of k boxes, k >= 1), remove them and get k*k points.
Find the maximum points you can get.
Example 1:
Input:
[1, 3, 2, 2, 2, 3, 4, 3, 1]
Output:
23
Explanation:
[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----> [1, 3, 3, 4, 3, 1] (3*3=9 points) 
----> [1, 3, 3, 3, 1] (1*1=1 points) 
----> [1, 1] (3*3=9 points) 
----> [] (2*2=4 points)
Note: The number of boxes n would not exceed 100.
X.
http://www.lydxlx.net/2017/03/26/first-post/
The above DP solution seems to run in  time as there are  states for  and each state roughly takes  time in average to transit. However, the bound is not tight, and the tight one is , which can be shown via a more careful analysis.
We cluster  into several clusters based on the the value of . Say there are in total  clusters, and the -cluster contains  indices of . We then have . When we fix a cluster, there can be at most different states involved. Since different clusters are disjoint, the total number of meaningful states is also bounded by .

http://www.cnblogs.com/grandyang/p/6850657.html
在之前帖子Reverse Pairs的讲解中,大神归纳了两种重现模式,我们这里也试着看能不能套用上。对于这种看来看去都没思路的题来说,抽象建模的能力就非常的重要了。对于题目中的具体场景啊,具体代表的东西我们都可忽略不看,这样能帮助我们接近问题的本质,这道题的本质就是一个数组,我们每次消去一个或多个数字,并获得相应的分数,让我们求最高能获得的分数。而之前那道Zuma Game也是给了一个数组,让我们往某个位置加数字,使得相同的数字至少有3个才能消除,二者是不是很像呢,但是其实解法却差别很大。那道题之所以暴力破解没有问题是因为数组的长度和给定的数字个数都有限制,而且都是相对较小的数,那么即便遍历所有情况也不会有太大的计算量。而这道题就不一样了,既然不能暴力破解,那么对于这种玩数组和子数组的题,刷题老司机们都会优先考虑用DP来做吧。既然要玩子数组,肯定要限定子数组的范围,那么至少应该是个二维的dp数组,其中dp[i][j]表示在子数组[i, j]范围内所能得到的最高的分数,那么最后我们返回dp[0][n-1]就是要求的结果。

那么对于dp[i][j]我们想,如果我们移除boxes[i]这个数字,那么总得分应该是1 + dp[i+1][j],但是通过分析题目中的例子,能够获得高积分的trick是,移除某个或某几个数字后,如果能使得原本不连续的相同数字变的连续是坠好的,因为同时移除的数字越多,那么所得的积分就越高。那么假如在[i, j]中间有个位置m,使得boxes[i]和boxes[m]相等,那么我们就不应该只是移除boxes[i]这个数字,而是还应该考虑直接移除[i+1, m-1]区间上的数,使得boxes[i]和boxes[m]直接相邻,那么我们获得的积分就是dp[i+1][m-1],那么我们剩余了什么,boxes[i]和boxes[m, j]区间的数,此时我们无法处理子数组[m, j],因为我们有些信息没有包括在我们的dp数组中,此类的题目归纳为不自己包含的子问题,其解法依赖于一些子问题以外的信息。这类问题通常没有定义好的重现关系,所以不太容易递归求解。为了解决这类问题,我们需要修改问题的定义,使得其包含一些外部信息,从而变成自包含子问题

那么对于这道题来说,无法处理boxes[m, j]区间是因为其缺少了关键信息,我们不知道boxes[m]左边相同数字的个数k,只有知道了这个信息,那么m的位置才有意义,所以我们的dp数组应该是一个三维数组dp[i][j][k],表示区间[i, j]中能获得的最大积分,当boxes[i]左边有k个数字跟其相等,那么我们的目标就是要求dp[0][n-1][0]了,而且我们也能推出dp[i][i][k] = (1+k) * (1+k)这个等式。那么我们来推导重现关系,对于dp[i][j][k],如果我们移除boxes[i],那么我们得到(1+k)*(1+k) + dp[i+1][j][0]。对于上面提到的那种情况,当某个位置m,有boxes[i] == boxes[m]时,我们也应该考虑先移除[i+1,m-1]这部分,我们得到积分dp[i+1][m-1][0],然后再处理剩下的部分,得到积分dp[m][j][k+1],这里k加1点原因是,移除了中间的部分后,原本和boxes[m]不相邻的boxes[i]现在相邻了,又因为二者值相同,所以k应该加1,因为k的定义就是左边相等的数字的个数。讲到这里,那么DP方法最难的递推公式也就得到了,那么代码就不难写了,需要注意的是,这里的C++的写法不能用vector来表示三维数组,好像是内存限制超出,只能用C语言的写法,由于C语言数组的定义需要初始化大小,而题目中说了数组长度不会超100,所以我们就用100来初始化
    int removeBoxes(vector<int>& boxes) {
        int n = boxes.size();
        int dp[100][100][100] = {0};
        return helper(boxes, 0, n - 1, 0, dp);
    }
    int helper(vector<int>& boxes, int i, int j, int k, int dp[100][100][100]) {
        if (j < i) return 0;
        if (dp[i][j][k] > 0) return dp[i][j][k];
        int res = (1 + k) * (1 + k) + helper(boxes, i + 1, j, 0, dp);
        for (int m = i + 1; m <= j; ++m) {
            if (boxes[m] == boxes[i]) {
                res = max(res, helper(boxes, i + 1, m - 1, 0, dp) + helper(boxes, m, j, k + 1, dp));
            }
        }
        return dp[i][j][k] = res;
    }
https://discuss.leetcode.com/topic/84300/java-dp-memorization-60ms
When facing this problem, I am keeping thinking how to simulate the case when boxes[i] == boxes[j] when i and j are not consecutive. It turns out that the dp matrix needs one more dimension to store such state. So we are going to define the state as
dp[i][j][k] represents the max points from box[i] to box[j] with k boxes whose values equal to box[i]
The transformation function is as below
dp[i][j][k] = max(dp[i+1][m-1][1] + dp[m][j][k+1]) when box[i] = box[m]
From your explanation
dp[i][j][k] represents the max points from box[i] to box[j] with k boxes whose values equal to box[i]
However, I think dp[i][j][k] should mean the max points from box[i] to box[j] with k boxes of value box[i] merged.
And also the DP
We have two condition
  1. We choose to merge k boxes
this mean we would have score = dp(i+1, j, 1) + k * k ...............(1)
  1. We don't merge k boxes
    so, we can continue to find box which is the same
    this means when we find box m equal to box i, we can have one more box, so k become k + 1
    So we have dp(i+1, m-1, 1) + dp (m, j, k + 1) ...............(2)
    the first term is the other boxes
    and the second term contain information of the same boxes(box[i] or box[m]) we have found till now
dp[i][j][k] = max ((1), (2))
  public int removeBoxes(int[] boxes) {
        if (boxes == null || boxes.length == 0) {
            return 0;
        }

        int size = boxes.length;
        int[][][] dp = new int[size][size][size];

        return get(dp, boxes, 0, size-1, 1);
    }

    private int get(int[][][] dp, int[] boxes, int i, int j, int k) {
        if (i > j) {
            return 0;
        } else if (i == j) {
            return k * k;
        } else if (dp[i][j][k] != 0) {
            return dp[i][j][k];
        } else {
            int temp = get(dp, boxes, i + 1, j, 1) + k * k;

            for (int m = i + 1; m <= j; m++) {
                if (boxes[i] == boxes[m]) {
                    temp = Math.max(temp, get(dp, boxes, i + 1, m - 1, 1) + get(dp, boxes, m, j, k + 1));
                }
            }

            dp[i][j][k] = temp;
            return temp;
        }


    }
X.
http://www.codingblog.cn/blog/34458.html
http://blog.csdn.net/yy254117440/article/details/67638980
整体思路类似于分治和记忆化存储
三维dp,直接看下面这种情况:
   1 2 3 4 2 2 
  • 1
  • 1
用dp[i][j][k] 存储可获得的最大分数,其中i是左边界,j是又边界,k是和右边界相等的后缀长度。上面例子如下:
   1 2 3 4 2 2
   i       j   即dp[i][j][1]
  • 1
  • 2
  • 1
  • 2
对于当前左右边界和相应的k值,可以对右边界后k个元素进行merge操作得分:
dfs(boxes, mem, l, r - 1, 0 ) + (k + 1) * (k + 1);
  • 1
  • 1
也可以不merge,从左往右如果找到一个值和box[r]相等则将原数组分为两部分求值:
   1 2 2 2 左右两部分合并
   i j    dp[i][j][2] 
   3 4    中间的部分
   i j    dp[i][j][0]
  • 1
  • 2
  • 3
  • 4
  • 1
  • 2
  • 3
  • 4
Math.max(mem[l][r][k], dfs(boxes, mem, l, i, k + 1) + dfs(boxes, mem, i + 1, r - 1, 0));
    public int removeBoxes(int[] boxes) { int size = boxes.length; int[][][] mem = new int[size][size][size]; return dfs(boxes, mem, 0, size - 1, 0); } private int dfs(int[] boxes, int[][][] mem, int l, int r, int k) { if (l > r) return 0; if (mem[l][r][k] > 0) return mem[l][r][k]; while (r > l && boxes[r] == boxes[r - 1]) { r--; k++; } mem[l][r][k] = dfs(boxes, mem, l, r - 1, 0 ) + (k + 1) * (k + 1); for (int i = l; i < r; i++) { if (boxes[i] == boxes[r]) { mem[l][r][k] = Math.max(mem[l][r][k], dfs(boxes, mem, l, i, k + 1) + dfs(boxes, mem, i + 1, r - 1, 0)); } } return mem[l][r][k]; }

    http://www.codingblog.cn/blog/34458.html
        /* l: 最左位置
         * r: 最右位置
         * same_len : 在r后面且与r相同的元素的长度
         * rec: 记录从l到r的后缀长度为same_len时的消除值
         * boxes: 所有盒子的颜色值
         * 返回最终的最大的盒子值
         */
        int dfs(int l, int r, int same_len, int rec[100][100][100], vector<int>& boxes){
            if(l>r) return 0;
            // 已经遍历过不需要再遍历
            if(rec[l][r][same_len] > 0) 
                return rec[l][r][same_len];
            while(r>l && boxes[r] == boxes[r-1]){
                r--;
                same_len++;
            }
            rec[l][r][same_len] = (same_len+1)*(same_len+1) + dfs(l,r-1,0,rec,boxes);
            for(int i = l; i < r;i++)
                if(boxes[i] == boxes[r])
                    // 如果发现这个值跟最右的值相等,存在两种可能
                    // 先消除最右的元素及其后缀元素的长度
                    // 消除当前值和最右值中间的元素再消除相同的元素值和当前元素值前面的元素
                    rec[l][r][same_len] = max(rec[l][r][same_len], dfs(l,i,same_len+1,rec,boxes)+dfs(i+1,r-1,0,rec,boxes)); 
    
            return rec[l][r][same_len];
    
        }
    https://mikecoder.github.io/oj-code/2017/05/06/RemoveBoxes/
    Think about using a DP[100][100][100] to store the status that from [left] to [right] we have [k] same numbers in the end.
    So, we can find the status transition way:

    DP[left][right][k] = max(DP[left][right][k], DFS(boxes, left, i, k + 1) + DFS(boxes, i + 1, right - 1, 0));
    http://www.cnblogs.com/heisenberg-/p/6789708.html
    http://blog.csdn.net/raorang/article/details/72584957
      memo[l][r][k] = max(memo[l][r][k], dfs(boxes,memo,l,i,k+1) + dfs(boxes,memo,i+1,r-1,0));
    意思是在序列的l-r部分后接k长度的 r值序列 所能得到的最大得分。
    https://discuss.leetcode.com/topic/84687/java-top-down-and-bottom-up-dp-solutions
    Finally here are the two solutions, one for top-down DP and the other for bottom-up DP. From the bottom-up solution, the time complexity will be O(n^4) and the space complexity will be O(n^3).
    Top-down DP:
    public int removeBoxes(int[] boxes) {
        int n = boxes.length;
        int[][][] dp = new int[n][n][n];
        return removeBoxesSub(boxes, 0, n - 1, 0, dp);
    }
        
    private int removeBoxesSub(int[] boxes, int i, int j, int k, int[][][] dp) {
        if (i > j) return 0;
        if (dp[i][j][k] > 0) return dp[i][j][k];
            
        int res = (k + 1) * (k + 1) + removeBoxesSub(boxes, i + 1, j, 0, dp);
            
        for (int m = i + 1; m <= j; m++) {
            if (boxes[i] == boxes[m]) {
                res = Math.max(res, removeBoxesSub(boxes, i + 1, m - 1, 0, dp) + removeBoxesSub(boxes, m, j, k + 1, dp));
            }
        }
            
        dp[i][j][k] = res;
        return res;
    }

    X.
    下面这种写法是上面解法的迭代方式,但是却有一些不同,这里我们需要对dp数组的部分值做一些初始化,将每个数字的所有k值的情况的积分都先算出来,然后在整体更新三维dp数组的时候也很有意思,并不是按照原有的顺序更新,而是块更新,先更新dp[1][0][k], dp[2][1][k], dp[3][2][k]....,再更新dp[2][0][k], dp[3][1][k], dp[4][2][k]...., 再更新dp[3][0][k], dp[4][1][k], dp[5][2][k]....,之前好像也有一道是这样区域更新的题

        int removeBoxes(vector<int>& boxes) {
            int n = boxes.size();
            int dp[n][n][n] = {0};
            for (int i = 0; i < n; ++i) {
                for (int k = 0; k <= i; ++k) {
                    dp[i][i][k] = (1 + k) * (1 + k);
                }   
            }
            for (int t = 1; t < n; ++t) {
                for (int j = t; j < n; ++j) {
                    int i = j - t;
                    for (int k = 0; k <= i; ++k) {
                        int res = (1 + k) * (1 + k) + dp[i + 1][j][0];
                        for (int m = i + 1; m <= j; ++m) {
                            if (boxes[m] == boxes[i]) {
                                res = max(res, dp[i + 1][m - 1][0] + dp[m][j][k + 1]);
                            }
                        }
                        dp[i][j][k] = res;
                    }
                }
            }
            return n == 0 ? 0 : dp[0][n - 1][0];
        }


    首先把连续相同颜色的盒子进行合并,得到数组color以及数组length,分别表示合并后盒子的颜色和长度。
    dp[l][r][k]表示第l到第r个合并后的盒子,连同其后颜色为color[r]的长度k一并消去所能得到的最大得分。
    dp[l][r][k] = dp[l][r - 1][0] + (length[r] + k) ** 2
    
    dp[l][r][k] = max(dp[l][r][k], dp[l][i][length[r] + k] + dp[i + 1][r - 1][0])  其中 i ∈[l, r - 1]



    No comments:

    Post a Comment

    Labels

    GeeksforGeeks (1109) LeetCode (1095) Review (846) Algorithm (795) to-do (634) LeetCode - Review (574) Classic Algorithm (324) Dynamic Programming (294) Classic Interview (288) Google Interview (242) Tree (145) POJ (139) Difficult Algorithm (132) LeetCode - Phone (127) EPI (125) Bit Algorithms (120) Different Solutions (120) Lintcode (113) Cracking Coding Interview (110) Smart Algorithm (109) Math (108) HackerRank (89) Binary Search (83) Binary Tree (82) Graph Algorithm (76) Greedy Algorithm (73) DFS (71) Stack (65) LeetCode - Extended (62) Interview Corner (61) List (58) Advanced Data Structure (56) BFS (54) Codility (54) ComProGuide (52) Algorithm Interview (50) Geometry Algorithm (49) Trie (49) Binary Search Tree (47) USACO (46) Interval (45) LeetCode Hard (42) Mathematical Algorithm (42) ACM-ICPC (41) Data Structure (40) Knapsack (40) Space Optimization (40) Jobdu (39) Matrix (39) Recursive Algorithm (39) String Algorithm (38) Union-Find (37) Backtracking (36) Codeforces (36) Introduction to Algorithms (36) Must Known (36) Beauty of Programming (35) Sort (35) Array (33) Data Structure Design (33) Segment Tree (33) Sliding Window (33) prismoskills (33) HDU (31) Priority Queue (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) Graph (27) Random (27) Company - LinkedIn (25) GeeksQuiz (25) Logic Thinking (25) Post-Order Traverse (25) Pre-Sort (25) Time Complexity (25) hihocoder (25) Queue (24) Company-Facebook (23) High Frequency (23) TopCoder (23) Algorithm Game (22) Binary Indexed Trees (22) Bisection Method (22) Hash (22) DFS + Review (21) Lintcode - Review (21) Two Pointers (21) Brain Teaser (20) CareerCup (20) Company - Twitter (20) LeetCode - DP (20) Merge Sort (20) O(N) (20) Follow Up (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) KMP (14) LeetCode - DFS (14) Number (14) Number Theory (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Euclidean GCD (13) Long Increasing Sequence(LIS) (13) Majority (13) Reverse Thinking (13) mitbbs (13) Combination (12) Computational Geometry (12) LeetCode - Classic (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) Miscs (11) Princeton (11) Proof (11) Rolling Hash (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) SPOJ (10) Theory (10) TreeMap (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) 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) 穷竭搜索 (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) Level Order Traversal (7) Math-Divisible (7) Probability DP (7) Quick Select (7) Radix Sort (7) TreeSet (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) 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) LeetCode - TODO (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) 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) 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) 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) 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) 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) 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) 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) 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) 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 - Thinking (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) 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