Saturday, May 12, 2018

LeetCode 688 - Knight Probability in Chessboard


https://leetcode.com/problems/knight-probability-in-chessboard/
On an NxN chessboard, a knight starts at the r-th row and c-th column and attempts to make exactly K moves. The rows and columns are 0 indexed, so the top-left square is (0, 0), and the bottom-right square is (N-1, N-1).
A chess knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Each time the knight is to move, it chooses one of eight possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.
The knight continues moving until it has made exactly K moves or has moved off the chessboard. Return the probability that the knight remains on the board after it has stopped moving.
Example:
Input: 3, 2, 0, 0
Output: 0.0625
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.
Note:

  • N will be between 1 and 25.
  • K will be between 0 and 100.
  • The knight always initially starts on the board.

  • https://leetcode.com/problems/knight-probability-in-chessboard/solution/
    Let f[r][c][steps] be the probability of being on square (r, c) after steps steps. Based on how a knight moves, we have the following recursion:
    f[r][c][steps] = \sum_{dr, dc} f[r+dr][c+dc][steps-1] / 8.0
    where the sum is taken over the eight (dr, dc) pairs (2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2).
    Instead of using a three-dimensional array f, we will use two two-dimensional ones dp and dp2, storing the result of the two most recent layers we are working on. dp2 will represent f[][][steps], and dp will represent f[][][steps-1].
    • Time Complexity: O(N^2 K) where N, K are defined as in the problem. We do O(1) work on each layer dp of N^2 elements, and there are K layers considered.
    • Space Complexity: O(N^2), the size of dp and dp2.
    It's no need to create 'double[][] dp1' inside the loop. Create it outside and reuse it, swap 'dp0' and 'dp1' after calculating.
        public double knightProbability(int N, int K, int sr, int sc) {
            double[][] dp = new double[N][N];
            int[] dr = new int[]{2, 2, 1, 1, -1, -1, -2, -2};
            int[] dc = new int[]{1, -1, 2, -2, 2, -2, 1, -1};

            dp[sr][sc] = 1;
            for (; K > 0; K--) {
                double[][] dp2 = new double[N][N];
                for (int r = 0; r < N; r++) {
                    for (int c = 0; c < N; c++) {
                        for (int k = 0; k < 8; k++) {
                            int cr = r + dr[k];
                            int cc = c + dc[k];
                            if (0 <= cr && cr < N && 0 <= cc && cc < N) {
                                dp2[cr][cc] += dp[r][c] / 8.0;
                            }
                        }
                    }
                }
                dp = dp2;
            }
            double ans = 0.0;
            for (double[] row: dp) {
                for (double x: row) ans += x;
            }
            return ans;
        }
    https://leetcode.com/problems/knight-probability-in-chessboard/discuss/108214/My-easy-understand-dp-solution
        private int[][] dirs = new int[][]{{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
        public double knightProbability(int N, int K, int r, int c) {
            double[][][] dp = new double[K + 1][N][N];
            dp[0][r][c] = 1;
            for (int step = 1; step <= K; step++) {
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        for (int[] dir : dirs) {
                            int x = dir[0] + i;
                            int y = dir[1] + j;
                            if (x < 0 || x >= N || y < 0 || y >= N) continue;
                            dp[step][i][j] += dp[step - 1][x][y] * 0.125;
                        }
                    }
                }
            }
            double res = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    res += dp[K][i][j];
                }
            }
            return res;
        }


    X. https://leetcode.com/problems/knight-probability-in-chessboard/discuss/113954/Evolve-from-recursive-to-dpbeats-94
    recursive version(TLE):
    class Solution {
        private int[][]dir = new int[][]{{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};
        public double knightProbability(int N, int K, int r, int c) {
            return find(N,K,r,c);
        }
        public double find(int N,int K,int r,int c){
            if(r < 0 || r > N - 1 || c < 0 || c > N - 1) return 0;
            if(K == 0)  return 1;
            double rate = 0;
            for(int i = 0;i < dir.length;i++){
                rate += 0.125 * find(N,K - 1,r + dir[i][0],c + dir[i][1]);
            }
            return rate;
        }
    }
    
    dp version:
    class Solution {
        private int[][]dir = new int[][]{{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};
        private double[][][] dp;
        public double knightProbability(int N, int K, int r, int c) {
            dp = new double[N][N][K + 1];
            return find(N,K,r,c);
        }
        public double find(int N,int K,int r,int c){
            if(r < 0 || r > N - 1 || c < 0 || c > N - 1) return 0;
            if(K == 0)  return 1;
            if(dp[r][c][K] != 0) return dp[r][c][K];
            double rate = 0;
            for(int i = 0;i < dir.length;i++)   rate += 0.125 * find(N,K - 1,r + dir[i][0],c + dir[i][1]);
            dp[r][c][K] = rate;
            return rate;
        }
    }

    X. BFS + Path Compression

    private static final int[][] direction = new int[][] { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, 1 }, { 2, -1 }, { -2, 1 },
        { -2, -1 } };

    // k moves, n*n board, starts at r, c
    // n, k starts with 1
    public double knightProbability(int n, int k, int r, int c) {

      Queue<Element> queue = new ArrayDeque<>();
      queue.add(new Element(r, c, 1));

      while (k > 0) {
        k--;
        int size = queue.size();
        Map<Integer, Double> cache = new HashMap<>();
        for (int i = 0; i < size; i++) {
          Element cur = queue.poll();
          for (int j = 0; j < direction.length; j++) {
            int newRol = cur.row + direction[j][0];
            int newCol = cur.col + direction[j][1];
            if (isValid(newRol, newCol, n)) {
              int key = newRol * n + newCol;
              cache.put(key, cache.getOrDefault(key, 0d) + cur.prob / 8);
            }
            // queue.add(new Element(newRol, newCol, cur.step + 1, cur.prob / 8));
          }
        }

        for (Entry<Integer, Double> entry : cache.entrySet()) {
          queue.add(new Element(entry.getKey() / n, entry.getKey() % n, entry.getValue()));
        }
      }

      double totalPro = 0;
      // for (int i = 0; i < queue.size(); i++) {
      while (!queue.isEmpty()) {
        totalPro += queue.poll().prob;
      }
      return totalPro;
    }

    private boolean isValid(int row, int col, int n) {
      return row >= 0 && row <= n - 1 && col >= 0 && col <= n - 1;
    }

    private static class Element {
      public final int row, col;
      public double prob;

      public Element(int row, int col, double prob) {
        super();
        this.row = row;
        this.col = col;
        this.prob = prob;
      }

      @Override
      public String toString() {
        return "Element [row=" + row + ", col=" + col + ", prob=" + prob + "]";
      }
    }
    X. Approach #2: Matrix Exponentiation
    The recurrence expressed in Approach #1 expressed states that transitioned to a linear combination of other states. Any time this happens, we can represent the entire transition as a matrix of those linear combinations. Then, the n-th power of this matrix represents the transition of n moves, and thus we can reduce the problem to a problem of matrix exponentiation.
    Algorithm
    First, there is a lot of symmetry on the board that we can exploit. Naively, there are N^2 possible states the knight can be in (assuming it is on the board). Because of symmetry through the horizontal, vertical, and diagonal axes, we can assume that the knight is in the top-left quadrant of the board, and that the column number is equal to or larger than the row number. For any square, the square that is found by reflecting about these axes to satisfy these conditions will be the canonical index of that square.
    This will reduce the number of states from N^2 to approximately \frac{N^2}{8}, which makes the following (cubic) matrix exponentiation on this O(\frac{N^2}{8}) \times O(\frac{N^2}{8}) matrix approximately 8^3 times faster.
    Now, if we know that every state becomes some linear combination of states after one move, then let's write a transition matrix \mathcal{T} of them, where the i-th row of \mathcal{T} represents the linear combination of states that the i-th state goes to. Then, \mathcal{T}^n represents a transition of n moves, for which we want the sum of the i-th row, where iis the index of the starting square.
    • Time Complexity: O(N^6 \log(K)) where N, K are defined as in the problem. There are approximately \frac{N^2}{8}canonical states, which makes our matrix multiplication O(N^6). To find the K-th power of this matrix, we make O(\log(K)) matrix multiplications.
    • Space Complexity: O(N^4). The matrix has approximately \frac{N^4}{64} elements.

        public double knightProbability(int N, int K, int sr, int sc) {
            int[] dr = new int[]{-1, -1, 1, 1, -2, -2, 2, 2};
            int[] dc = new int[]{2, -2, 2, -2, 1, -1, 1, -1};

            int[] index = new int[N * N];
            int t = 0;
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    if (r * N + c == canonical(r, c, N)) {
                        index[r * N + c] = t;
                        t++;
                    } else {
                        index[r * N + c] = index[canonical(r, c, N)];
                    }
                }
            }

            double[][] T = new double[t][t];
            int curRow = 0;
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    if (r * N + c == canonical(r, c, N)) {
                        for (int k = 0; k < 8; k++) {
                            int cr = r + dr[k], cc = c + dc[k];
                            if (0 <= cr && cr < N && 0 <= cc && cc < N) {
                                T[curRow][index[canonical(cr, cc, N)]] += 0.125;
                            }
                        }
                        curRow++;
                    }
                }
            }

            double[] row = matrixExpo(T, K)[index[sr*N + sc]];
            double ans = 0.0;
            for (double x: row) ans += x;
            return ans;
        }

        public int canonical(int r, int c, int N) {
            if (2*r > N) r = N-1-r;
            if (2*c > N) c = N-1-c;
            if (r > c) {
                int t = r;
                r = c;
                c = t;
            }
            return r * N + c;
        }
        public double[][] matrixMult(double[][] A, double[][] B) {
            double[][] ans = new double[A.length][A.length];
            for (int i = 0; i < A.length; i++) {
                for (int j = 0; j < B[0].length; j++) {
                    for (int k = 0; k < B.length; k++) {
                        ans[i][j] += A[i][k] * B[k][j];
                    }
                }
            }
            return ans;
        }
        public double[][] matrixExpo(double[][] A, int pow) {
            double[][] ans = new double[A.length][A.length];
            for (int i = 0; i < A.length; i++) ans[i][i] = 1;
            if (pow == 0) return ans;
            if (pow == 1) return A;
            if (pow % 2 == 1) return matrixMult(matrixExpo(A, pow-1), A);
            double[][] B = matrixExpo(A, pow / 2);
            return matrixMult(B, B);
        }



    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