Thursday, May 24, 2018

Leetcode 723 Candy Crush


http://bookshadow.com/weblog/2017/11/05/leetcode-candy-crush/
This question is about implementing a basic elimination algorithm for Candy Crush.
Given a 2D integer array board representing the grid of candy, different positive integers board[i][j]represent different types of candies. A value of board[i][j] = 0 represents that the cell at position (i, j) is empty. The given board represents the state of the game following the player's move. Now, you need to restore the board to a stable state by crushing candies according to the following rules:
  1. If three or more candies of the same type are adjacent vertically or horizontally, "crush" them all at the same time - these positions become empty.
  2. After crushing all candies simultaneously, if an empty space on the board has candies on top of itself, then these candies will drop until they hit a candy or bottom at the same time. (No new candies will drop outside the top boundary.)
  3. After the above steps, there may exist more candies that can be crushed. If so, you need to repeat the above steps.
  4. If there does not exist more candies that can be crushed (ie. the board is stable), then return the current board.
You need to perform the above rules until the board becomes stable, then return the current board.
Example 1:
Input:
board = 
[[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,2,1,2,2],[4,1,4,4,1014]]
Output:
[[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]
Explanation: 

Note:
  1. The length of board will be in the range [3, 50].
  2. The length of board[i] will be in the range [3, 50].
  3. Each board[i][j] will initially start as an integer in the range [1, 2000].
模拟实现游戏“糖果粉碎传奇”
给定二维数组board,每行、列中3个或以上连续相同的数字都可以被消去(变为0表示空位),消去后位于上方的数字会填充空位。
重复直到没有更多的数字可以被消去。


模拟题
循环,把拟被消去的数字替换为其相反数,遍历每一列,自底向上遍历每一行,将负数消去。
当某一次消去未找到任何数字时,循环终止。
https://github.com/joy32812/leetcode/blob/master/src/com/leetcode/P723_CandyCrush.java
  int m, n;
  int[][] B;

  public int[][] candyCrush(int[][] board) {

    B = board;
    m = B.length;
    n = B[0].length;

    while (crash()) {
      drop();
    }

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        System.out.print(B[i][j] + " ");
      }
      System.out.println();
    }
    return B;
  }

  private boolean crash() {

    boolean[][] c = new boolean[m][n];
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (B[i][j] == 0)
          continue;

        int cnt = 1;
        // right
        for (int k = j + 1; k < n; k++) {
          if (B[i][k] == B[i][j])
            cnt++;
          else
            break;
        }

        if (cnt >= 3) {
          for (int k = j; k < n && k < j + cnt; k++) {
            c[i][k] = true;
          }
        }

        // down
        cnt = 1;
        for (int k = i + 1; k < m; k++) {
          if (B[i][j] == B[k][j])
            cnt++;
          else
            break;
        }

        if (cnt >= 3) {
          for (int k = i; k < m && k < i + cnt; k++) {
            c[k][j] = true;
          }
        }
      }
    }

    boolean crash = false;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (c[i][j]) {
          crash = true;
          B[i][j] = 0;
        }
      }
    }

    return crash;
  }

  private void drop() {
    for (int j = 0; j < n; j++) {

      int now = m - 1;
      for (int i = m - 1; i >= 0; i--) {
        if (B[i][j] == 0)
          continue;
        int tp = B[i][j];
        B[i][j] = B[now][j];
        B[now][j] = tp;
        now--;
      }

    }

  }
http://www.cnblogs.com/grandyang/p/7858414.html
这道题就是糖果消消乐,博主刚开始做的时候,没有看清楚题意,以为就像游戏中的那样,每次只能点击一个地方,然后消除后糖果落下,这样会导致一个问题,就是原本其他可以消除的地方在糖果落下后可能就没有了,所以博主在想点击的顺序肯定会影响最终的stable的状态,可是题目怎么没有要求返回所剩糖果最少的状态?后来发现,其实这道题一次消除table中所有可消除的糖果,然后才下落,形成新的table,这样消除后得到的结果就是统一的了,这样也大大的降低了难度。下面就来看如何找到要消除的糖果,可能有人会想像之前的岛屿的题目一样找连通区域,可是这道题的有限制条件,只有横向或竖向相同的糖果数达到三个才能消除,并不是所有的连通区域都能消除,所以找连通区域不是一个好办法。最好的办法其实是每个糖果单独检查其是否能被消除,然后把所有能被删除的糖果都标记出来统一删除,然后在下落糖果,然后再次查找,直到无法找出能够消除的糖果时达到稳定状态。好,那么我们用一个数组来保存可以被消除的糖果的位置坐标,判断某个位置上的糖果能否被消除的方法就是检查其横向和纵向的最大相同糖果的个数,只要有一个方向达到三个了,当前糖果就可以被消除。所以我们对当前糖果的上下左右四个方向进行查看,用四个变量x0, x1, y0, y1,其中x0表示上方相同的糖果的最大位置,x1表示下方相同糖果的最大位置,y0表示左边相同糖果的最大位置,y1表示右边相同糖果的最大位置,均初始化为当前糖果的位置,然后使用while循环向每个方向遍历,注意我们并不需要遍历到头,而是只要遍历三个糖果就行了,因为一旦查到了三个相同的,就说明当前的糖果已经可以消除了,没必要再往下查了。查的过程还要注意处理越界情况,好,我们得到了上下左右的最大的位置,分别让相同方向的做差,如果水平和竖直方向任意一个大于3了,就说明可以消除,将坐标加入数组del中。注意这里一定要大于3,是因为当发现不相等退出while循环时,坐标值已经改变了,所以已经多加了或者减了一个,所以差值要大于3。遍历完成后,如果数组del为空,说明已经stable了,直接break掉,否则将要消除的糖果位置都标记为0,然后进行下落处理。下落处理实际上是把数组中的0都移动到开头,那么就从数组的末尾开始遍历,用一个变量t先指向末尾,然后然后当遇到非0的数,就将其和t位置上的数置换,然后t自减1,这样t一路减下来都是非0的数,而0都被置换到数组开头了
    vector<vector<int>> candyCrush(vector<vector<int>>& board) {
        int m = board.size(), n = board[0].size();
        while (true) {
            vector<pair<int, int>> del;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (board[i][j] == 0) continue;
                    int x0 = i, x1 = i, y0 = j, y1 = j;
                    while (x0 >= 0 && x0 > i - 3 && board[x0][j] == board[i][j]) --x0;
                    while (x1 < m && x1 < i + 3 && board[x1][j] == board[i][j]) ++x1;
                    while (y0 >= 0 && y0 > j - 3 && board[i][y0] == board[i][j]) --y0;
                    while (y1 < n && y1 < j + 3 && board[i][y1] == board[i][j]) ++y1;
                    if (x1 - x0 > 3 || y1 - y0 > 3) del.push_back({i, j});
                }
            }
            if (del.empty()) break;
            for (auto a : del) board[a.first][a.second] = 0;
            for (int j = 0; j < n; ++j) {
                int t = m - 1;
                for (int i = m - 1; i >= 0; --i) {
                    if (board[i][j]) swap(board[t--][j], board[i][j]);   
                }
            }
        }
        return board;
    }
https://www.codetd.com/article/154114
画图模拟比较好理解.
vector<vector<int>> candyCrush(vector<vector<int>>& board) { int m = board.size(); int n = board[0].size(); while (true) { vector<pair<int, int>> to_crash; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j]) { //为了减小计算量,元素为0的略过 int i1 = i, i0 = i, j1 = j, j0 = j; // i1,i0,j1,j0分别为向下,向上,向右,向左的检测 //对每个点(i,j),以其为中心,向上下或左右方向扩展,看是否有连续 while (i1 < m && i1 < i+3 && board[i1][j] == board[i][j]) i1++; while (i0 >= 0 && i0 > i-3 && board[i0][j] == board[i][j]) i0--; while (j1 < n && j1 < j+3 && board[i][j1] == board[i][j]) j1++; while (j0 >= 0 && j0 > j-3 && board[i][j0] == board[i][j]) j0--; if (i1-i0 > 3 || j1-j0 > 3) to_crash.push_back({i,j}); //上下或左右连续元素超过3,即符合 } } } if (to_crash.empty()) break; for (auto t : to_crash) board[t.first][t.second] = 0; //重点:将所有标记位置置0 for (int j = 0; j < n; j++) { //由于是自上往下消除,因此外层对j(纵坐标)循环 int t = m-1; //t用于记录新board的横坐标 for (int i = m-1; i >= 0; i--) { //从下往上,非0元素参与交换,每次交换后t上移 if (board[i][j]) swap(board[i][j], board[t--][j]); } } } return board; }
https://www.cnblogs.com/jxr041100/p/8440349.html
public int[][] candyCrush(int[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) return board;
        int cnt = 0;
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 0) continue;
                if (   (i > 0 && Math.abs(board[i-1][j]) == board[i][j] && (i < m - 1 && board[i+1][j] == board[i][j]))
                    || (i > 1 && Math.abs(board[i-1][j]) == board[i][j] && Math.abs(board[i-2][j]) == board[i][j])
                    || (i < m - 2 && board[i+1][j] == board[i][j] && board[i+2][j] == board[i][j])
                    || (j > 0 && Math.abs(board[i][j-1]) == board[i][j] && (j < n - 1 && board[i][j+1] == board[i][j]))
                    || (j > 1 && Math.abs(board[i][j-1]) == board[i][j] && Math.abs(board[i][j-2]) == board[i][j])
                    || (j < n - 2 && board[i][j+1] == board[i][j] && board[i][j+2] == board[i][j])) {
                    cnt++;
                    board[i][j] = -board[i][j];
                }
            }
        }
        for (int j = 0; j < n; j++) {
            int ptr = m - 1;
            for (int i = m - 1; i >= 0; i--) {
                if (board[i][j] > 0) {
                    board[ptr--][j] = board[i][j];
                }
            }
            for (int i = ptr; i >= 0; i--) {
                board[i][j] = 0;
            }
        }
        if (cnt == 0) {
            return board;
        } else {
            return candyCrush(board);
        }
    }
https://www.cnblogs.com/lightwindy/p/9744174.html
    vector<vector<int>> candyCrush(vector<vector<int>>& board) {
        const auto R = board.size(), C = board[0].size();
        bool changed = true;
         
        while (changed) {
            changed = false;
             
            for (int r = 0; r < R; ++r) {
                for (int c = 0; c + 2 < C; ++c) {
                    auto v = abs(board[r][c]);
                    if (v != 0 && v == abs(board[r][c + 1]) && v == abs(board[r][c + 2])) {
                        board[r][c] = board[r][c + 1] = board[r][c + 2] = -v;
                        changed = true;
                    }
                }
            }
             
            for (int r = 0; r + 2 < R; ++r) {
                for (int c = 0; c < C; ++c) {
                    auto v = abs(board[r][c]);
                    if (v != 0 && v == abs(board[r + 1][c]) && v == abs(board[r + 2][c])) {
                        board[r][c] = board[r + 1][c] = board[r + 2][c] = -v;
                        changed = true;
                    }
                }
            }
            for (int c = 0; c < C; ++c) {
                int empty_r = R - 1;
                for (int r = R - 1; r >= 0; --r) {
                    if (board[r][c] > 0) {
                        board[empty_r--][c] = board[r][c];
                    }
                }
                for (int r = empty_r; r >= 0; --r) {
                    board[r][c] = 0;
                }
            }
        }
         
        return board;
    }





X. http://storypku.com/2017/11/leetcode-question-723-candy-crush/
    vector<vector<int>> candyCrush(vector<vector<int>>& board) {
        int m = board.size(), n = board[0].size();
        bool toBeContinued = false;
        
        for (int i = 0; i < m; ++i) { // horizontal crushing
            for (int j = 0; j + 2 < n; ++j) {
                int& v1 = board[i][j];
                int& v2 = board[i][j+1];
                int& v3 = board[i][j+2];
                
                int v0 = std::abs(v1);
                
                if (v0 && v0 == std::abs(v2) && v0 == std::abs(v3)) {
                    v1 = v2 = v3 = - v0;
                    toBeContinued =  true;
                }
            }
        }
        
        for (int i = 0; i + 2 < m; ++i) {  // vertical crushing
            for (int j = 0; j < n; ++j) {
                int& v1 = board[i][j];
                int& v2 = board[i+1][j];
                int& v3 = board[i+2][j];
                int v0 = std::abs(v1);
                if (v0 && v0 == std::abs(v2) && v0 == std::abs(v3)) {
                    v1 = v2 = v3 = -v0;
                    toBeContinued = true;
                }
            }
        }
        
        for (int j = 0; j < n; ++j) { // gravity step
            int dropTo = m - 1;
            for (int i = m - 1; i >= 0; --i) {
                if (board[i][j] >= 0) {
                    board[dropTo--][j] = board[i][j];
                }
            }
            
            for (int i = dropTo; i >= 0; i--) {
                board[i][j] = 0;
            }
        }
        
        return toBeContinued ? candyCrush(board) : board;
        
    }





No comments:

Post a Comment

Labels

LeetCode (1243) GeeksforGeeks (1129) Review (896) Algorithm (764) LeetCode - Review (722) to-do (636) Dynamic Programming (340) Classic Algorithm (313) Classic Interview (266) Google Interview (246) Tree (146) POJ (141) Difficult Algorithm (129) LeetCode - Phone (127) EPI (125) Bit Algorithms (120) Different Solutions (117) Math (115) Lintcode (113) Cracking Coding Interview (110) Smart Algorithm (105) DFS (93) Binary Search (92) HackerRank (89) Greedy Algorithm (84) Binary Tree (83) Stack (78) Graph Algorithm (76) Two Pointers (64) BFS (63) LeetCode - Extended (62) Interview Corner (61) List (57) Advanced Data Structure (56) Geometry Algorithm (56) Interval (54) Codility (53) ComProGuide (52) LeetCode Hard (50) Trie (49) Union-Find (48) Binary Search Tree (47) Segment Tree (47) Algorithm Interview (46) USACO (46) Space Optimization (43) Bisection (42) Mathematical Algorithm (42) ACM-ICPC (41) Data Structure (40) Knapsack (40) Matrix (40) Time Complexity (40) Jobdu (39) Priority Queue (39) Recursive Algorithm (39) Sliding Window (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) prismoskills (33) Array (32) LeetCode - DP (32) HDU (31) Random (31) Google Code Jam (30) Graph (30) Permutation (30) Puzzles (30) Array O(N) (29) Company-Airbnb (29) Palindrome (29) Company-Zenefits (28) Pre-Sort (28) to-do-must (28) Logic Thinking (27) Microsoft 100 - July (27) Monotonic Stack (27) Queue (27) Binary Indexed Trees (26) Company - LinkedIn (25) Follow Up (25) GeeksQuiz (25) Post-Order Traverse (25) hihocoder (25) Company-Facebook (24) Algorithm Game (22) Hash (22) High Frequency (22) Merge Sort (22) DFS + Review (21) Lintcode - Review (21) O(N) (21) Brain Teaser (20) CareerCup (20) Company - Twitter (20) BST (19) Hard (19) Topological Sort (19) UVA (19) Sweep Line (18) Company-Uber (17) Game Theory (17) Left and Right Array (17) Probabilities (17) Proof (17) Codercareer (16) DP - Tree (16) Heap (16) Iterator (16) Shortest Path (16) String Search (16) Tree Traversal (16) itint5 (16) Difficult (15) KMP (15) Reverse Thinking (15) LeetCode - DFS (14) Number (14) Number Theory (14) Rolling Hash (14) TreeMap (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Computational Geometry (13) Euclidean GCD (13) LeetCode - Classic (13) Long Increasing Sequence(LIS) (13) Majority (13) mitbbs (13) Algorithm - How To (12) Combination (12) Fast Power Algorithm (12) LeetCode - Thinking (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) Simulation (12) 尺取法 (12) AOJ (11) Bucket Sort (11) DFS+Backtracking (11) DP - Interval (11) DP-Space Optimization (11) Divide and Conquer (11) Graph DFS (11) LCA (11) Math-Divisible (11) Miscs (11) O(1) Space (11) Prefix Sum (11) Princeton (11) X Sum (11) 挑战程序设计竞赛 (11) Coin Change (10) Company - Microsoft (10) DFS+Cache (10) DP - Bit Masking (10) DP - Digit (10) Facebook Hacker Cup (10) HackerRank Easy (10) Interval Tree (10) Kadane - Extended (10) MinMax (10) SPOJ (10) Theory (10) Tutorialhorizon (10) DP - Probability (9) DP-Multiple Relation (9) Mathblog (9) Max-Min Flow (9) Monotone Queue (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) Dijkstra (8) LeetCode - TODO (8) Linked List (8) Longest Common Subsequence(LCS) (8) Prime (8) Quick Select (8) Suffix Tree (8) Summary (8) Tech-Queries (8) Traversal Once (8) TreeSet (8) 穷竭搜索 (8) Algorithm Problem List (7) Expression (7) Facebook Interview (7) Fast Slow Pointers (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) One Pass (7) Pruning (7) Radix Sort (7) Tree DP (7) 蓝桥杯 (7) Bit Mask (6) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Monotone Queue (6) DP-Print Solution (6) Dutch Flag (6) Flood fill (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Manacher (6) Minimum Spanning Tree (6) Morris Traversal (6) Multiple Data Structures (6) Pre-Sum (6) Programming Pearls (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Stream (6) Suffix Array (6) Xpost (6) n00tc0d3r (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) Find Rule (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) Matrix Chain Multiplication (5) Maze (5) Microsoft Interview (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sudoku (5) Threaded (5) Word Search (5) jiuzhang (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) Greedy (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) 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) 男人八题 (4) A Star (3) Algorithm Design (3) B Tree (3) Bellman Ford (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) Factor (3) Finite Automata (3) Github (3) GoLang (3) Graph - Bipartite (3) Graph Coloring (3) Include vs Exclude (3) Islands (3) Joseph (3) K (3) Knapsack-多重背包 (3) Knight (3) LeetCode - Bit (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Median (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) Online Algorithm (3) Parentheses (3) Parser (3) Pascal's Triangle (3) Pattern Match (3) Programcreek (3) Project Euler (3) Rectangle (3) Robot (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) 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) Augmented BST (2) BOJ (2) BT - Path Sum (2) Balanced Binary Search Tree (2) Binary Search - Smart (2) Binomial Coefficient (2) Bit Counting (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Branch and Bound Method (2) Cache (2) Clock (2) Codesays (2) Company - Baidu (2) Company-Snapchat (2) Complete Binary Tree (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) Forward && Backward Scan (2) Game (2) GoHired (2) Graham Scan (2) Graph BFS+DFS (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) Jump Game (2) LeetCode - Hard (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) Math-Remainder Queue (2) Matrix Power (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) O(N) Hard (2) Object Design (2) Order Statistic Tree (2) Parent-Only Tree (2) Peak (2) PreProcess (2) Programming (2) Range Minimum Query (2) Regular Expression (2) Return Multiple Values (2) Reuse Forward Backward (2) Reverse (2) Rosettacode (2) Scan from right (2) Search (2) SimHash (2) Simple Algorithm (2) Sparse Table (2) Spatial Index (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Tree Without Tree Predefined (2) Two Pointers Window (2) Two-End-BFS (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) All Substrings (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Augmented Tree (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BFS - Priority Queue (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 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) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular (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) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS + RL (1) DFS+BFS, Flood Fill (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) EntryPoint (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (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) Knuth Shuffle (1) Kosaraju’s algorithm (1) Kruskal (1) Kth Element (1) Lazy (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) Lock (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 Multiplication (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 Steps (1) Multiple Tasks (1) Next Element (1) Next Successor (1) O(32N) (1) Offline Algorithm (1) Optimal Play (1) Optimization (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) 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) Recursion (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Remap (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Simplify (1) Sort && Binary Search (1) Space Complexity (1) Square (1) Strategy (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) Trade Off (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) cycl (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 英雄会 (1) 逆向思维 (1)

Popular Posts