Wednesday, September 21, 2016

LeetCode - 403 Frog Jump


https://leetcode.com/problems/frog-jump/
A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.
Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.
If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.
Note:
  • The number of stones is ≥ 2 and is < 1,100.
  • Each stone's position will be a non-negative integer < 231.
  • The first stone's position is always 0.
Example 1:
[0,1,3,5,6,8,12,17]

There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.

Return true. The frog can jump to the last stone by jumping 
1 unit to the 2nd stone, then 2 units to the 3rd stone, then 
2 units to the 4th stone, then 3 units to the 6th stone, 
4 units to the 7th stone, and 5 units to the 8th stone.
Example 2:
[0,1,2,3,4,8,9,11]

Return false. There is no way to jump to the last stone as 
the gap between the 5th and 6th stone is too large.

X. DP
http://www.cnblogs.com/grandyang/p/5888439.html
我们也可以用迭代的方法来解,用一个哈希表来建立每个石头和在该位置上能跳的距离之间的映射,建立一个一维dp数组,其中dp[i]表示在位置为i的石头青蛙的弹跳力(只有青蛙能跳到该石头上,dp[i]才大于0),由于题目中规定了第一个石头上青蛙跳的距离必须是1,为了跟后面的统一,我们对青蛙在第一块石头上的弹跳力初始化为0(虽然为0,但是由于题目上说青蛙最远能到其弹跳力+1的距离,所以仍然可以到达第二块石头)。我们用变量k表示当前石头,然后开始遍历剩余的石头,对于遍历到的石头i,我们来找到刚好能跳到i上的石头k,如果i和k的距离大于青蛙在k上的弹跳力+1,则说明青蛙在k上到不了i,则k自增1。我们从k遍历到i,如果青蛙能从中间某个石头上跳到i上,我们更新石头i上的弹跳力和最大弹跳力。这样当循环完成后,我们只要检查最后一个石头上青蛙的最大弹跳力是否大于0即可
    bool canCross(vector<int>& stones) {
        unordered_map<int, unordered_set<int>> m;
        vector<int> dp(stones.size(), 0);
        m[0].insert(0);
        int k = 0;
        for (int i = 1; i < stones.size(); ++i) {
            while (dp[k] + 1 < stones[i] - stones[k]) ++k;
            for (int j = k; j < i; ++j) {
                int t = stones[i] - stones[j];
                if (m[j].count(t - 1) || m[j].count(t) || m[j].count(t + 1)) {
                    m[i].insert(t);
                    dp[i] = max(dp[i], t);
                    break;
                }
            }
        }
        return dp.back() > 0;
    }



更好地做法是对于每个位置记录当前位置能向前走的距离,用一个map套set实现,90ms+
    public boolean canCross(int[] stones) {
        int len = stones.length;
        Map<Integer, HashSet<Integer>> map = new HashMap<>();
        for (int i = 0; i < len; i ++) {
            map.put(stones[i], new HashSet<>());
        }
        map.get(0).add(1);
        for (int i = 0; i < len - 1; i ++) {
            for (int step : map.get(stones[i])) {
                int to = step + stones[i];
                if (to == stones[len - 1]) {
                    return true;
                }
                HashSet<Integer> tmp = map.get(to);
                if (tmp != null) {
                    tmp.add(step);
                    if (step > 1) {
                        tmp.add(step - 1);
                    }
                    tmp.add(step + 1);
                }
            }
        }
        return false;
    }
https://discuss.leetcode.com/topic/59903/very-easy-to-understand-java-solution-with-explanations
Use map to represent a mapping from the stone (not index) to the steps that can be taken from this stone.
so this will be
[0,1,3,5,6,8,12,17]
{17=[], 0=[1], 1=[1, 2], 3=[1, 2, 3], 5=[1, 2, 3], 6=[1, 2, 3, 4], 8=[1, 2, 3, 4], 12=[3, 4, 5]}
Notice that no need to calculate the last stone.
On each step, we look if any other stone can be reached from it, if so, we update that stone's steps by adding step, step + 1, step - 1. If we can reach the final stone, we return true. No need to calculate to the last stone.
    public boolean canCross(int[] stones) {
        if (stones.length == 0) {
         return true;
        }
        
        HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>(stones.length);
        map.put(0, new HashSet<Integer>());
        map.get(0).add(1);
        for (int i = 1; i < stones.length; i++) {
         map.put(stones[i], new HashSet<Integer>() );
        }
        
        for (int i = 0; i < stones.length - 1; i++) {
         int stone = stones[i];
         for (int step : map.get(stone)) {
          int reach = step + stone;
          if (reach == stones[stones.length - 1]) {
           return true;
          }
          HashSet<Integer> set = map.get(reach);
          if (set != null) {
              set.add(step);
              if (step - 1 > 0) set.add(step - 1);
              set.add(step + 1);
          }
         }
        }
        
        return false;
    } 
I chose arraylist instead of map (map is better i tihnk), also I think we don't need loop to the stones.length, when current is already bigger than the reach, can prune mostly but still same in worst case.
public boolean canCross(int[] stones) {
    if(stones.length==2) return stones[1]-stones[0]==1;
    List<HashSet<Integer>> dp = new ArrayList<>(stones.length);
    for(int i=0;i<stones.length;i++)
        dp.add(new HashSet<Integer>());

    Iterator<Integer> kSet;
    dp.add(1, new HashSet<>(Arrays.asList(1)));

    for(int i=2;i<stones.length;i++){
        kSet = dp.get(i-1).iterator();
        int j=i, k=-1;
        while((k!=-1||kSet.hasNext())&&j<stones.length){

            if(k==-1) k = kSet.next();
            if(Math.abs(stones[j]-stones[i-1]-k)<=1)  //k reach point
            {
                if(j == stones.length-1) return true;
                HashSet<Integer> temp = dp.get(j);
                temp.add(stones[j]-stones[i-1]);
            }
            else if (j == stones.length-1||stones[j]-stones[i-1]-1>k)
                {k=-1;j=i-1;}
            j++;

        }

    }
    return false;
}
https://discuss.leetcode.com/topic/59423/simple-easy-to-understand-java-solution
public static boolean canCross(int[] stones) {
        Map<Integer, Set<Integer>> stoneMap = new HashMap<>();
        for (int i = 1; i < stones.length; i++) {
            stoneMap.put(stones[i], new HashSet<Integer>());
        }
        if(stones[0]+1 == stones[1]) {
            stoneMap.get(stones[1]).add(1);
        }
        for(int i = 1; i < stones.length; i++) {
            int eachStone = stones[i];
            for(Integer K: stoneMap.get(eachStone)) {
                if(K != 1 &&  stoneMap.containsKey(eachStone + K - 1)) {
                    stoneMap.get(eachStone + K - 1).add(K - 1);
                }
                if(stoneMap.containsKey(eachStone + K)) {
                    stoneMap.get(eachStone + K).add(K);
                }
                if(stoneMap.containsKey(eachStone + K + 1)) {
                    stoneMap.get(eachStone + K + 1).add(K + 1);
                }
            }
        }
        return stoneMap.get(stones[stones.length - 1]).size() >= 1;
    }
https://discuss.leetcode.com/topic/61561/simple-and-easy-understand-java-solution
http://www.voidcn.com/blog/tc_to_top/article/p-6237336.html


裸的n^2做法400ms+,lastPos[i]存到到i位置前可能的步长
    public boolean canCross(int[] stones) {
        int len = stones.length;
        if (len == 2 && stones[1] - stones[0] > 1) {
            return false;
        }
        Set[] lastPos = new Set[len + 1];
        for (int i = 1; i < len; i ++) {
            lastPos[i] = new HashSet<>();
        }
        lastPos[1].add(1);
        for (int i = 2; i < len; i ++) {
            for (int j = 1; j < i; j ++) {
                if (lastPos[j].size() > 0) {
                    int dist = stones[i] - stones[j];
                    if (lastPos[j].contains(dist) || lastPos[j].contains(dist - 1) || lastPos[j].contains(dist + 1)) {
                        lastPos[i].add(dist);
                    }
                }
            }
        }
        return lastPos[len - 1].size() > 0;
    }
public boolean canCross(int[] stones) 
        if (stones == null || stones.length == 0) {
            return false;
        }
        if (stones[1] > 1) {
            return false;
        }

        Set[] lastJump = new Set[stones.length];
        for (int i = 1; i < stones.length; i++) {
            lastJump[i] = new HashSet<Integer>();
        }
        lastJump[1].add(1);
        
        for (int i = 2; i < stones.length; i++) {
            for (int j = 1; j < i; j++) {
                //cell j can be reached
                if (lastJump[j].size() > 0) {
                    int currJump = stones[i] - stones[j];
                    if (lastJump[j].contains(currJump) || 
                        lastJump[j].contains(currJump + 1) ||
                        lastJump[j].contains(currJump - 1)) {
                        lastJump[i].add(currJump);
                    }
                }
            }
        }
        return lastJump[stones.length - 1].size() > 0;
    }

X. DFS
https://discuss.leetcode.com/topic/59439/straight-forward-9ms-7-line-c-solution-with-explanation
Search for the last stone in a depth-first way, prune those exceeding the [k-1,k+1] range. Well, I think the code is simple enough and need no more explanation.
bool canCross(vector<int>& stones, int pos = 0, int k = 0) {
    for (int i = pos + 1; i < stones.size(); i++) {
        int gap = stones[i] - stones[pos];
        if (gap < k - 1) continue;
        if (gap > k + 1) return false;
        if (canCross(stones, i, gap)) return true;
    }
    return pos == stones.size() - 1;
}
This can pass OJ at 9ms but is inefficient for extreme cases. (update: new test cases are added and the solution above no longer passes OJ, please see the solution below which takes 62ms) We can memorize the returns with minimum effort:
unordered_map<int, bool> dp;

bool canCross(vector<int>& stones, int pos = 0, int k = 0) {
    int key = pos | k << 11;

    if (dp.count(key) > 0)
        return dp[key];

    for (int i = pos + 1; i < stones.size(); i++) {
        int gap = stones[i] - stones[pos];
        if (gap < k - 1)
            continue;
        if (gap > k + 1)
            return dp[key] = false;
        if (canCross(stones, i, gap))
            return dp[key] = true;
    }

    return dp[key] = (pos == stones.size() - 1);
}
The number of stones is less than 1100 so pos will always be less than 2^11 (2048).
Stone positions could be theoretically up to 2^31 but k is practically not possible to be that big for the parameter as the steps must start from 0 and 1 and at the 1100th step the greatest valid k would be 1100. So combining pos and k is safe here.


https://discuss.leetcode.com/topic/59337/easy-version-java
public boolean canCross(int[] stones) {
        if(stones[1] > 1) return false;
        if(stones.length == 2) return true;
        return helper(stones, 1, 1);
    }
    private boolean helper(int[] arr, int i, int step){
        boolean pass = false;
        if(i == arr.length-1) return true;
        for(int j = i+1; j < arr.length; j++){
            if(arr[j] <= arr[i] + step + 1 && arr[j] >= arr[i]+step-1){
                pass = pass || helper(arr, j, arr[j] - arr[i]);
            }
        }
        return pass;
    }
http://blog.csdn.net/mebiuw/article/details/52577052
public boolean canCross(int[] stones) { int k = 0; return helper(stones, 0, k); } private boolean helper(int[] stones, int index, int k) { //目前已经达到了 if (index == stones.length - 1) return true; //选择k的步伐,范围k-1到k for (int i = k - 1; i <= k + 1; i++) { int nextJump = stones[index] + i; //看接下来有没有合适的石头可以跳过去,从接下来的位置中查找有没有nextJump的位置,有的话返回石头的编号 int nextPosition = Arrays.binarySearch(stones, index + 1, stones.length, nextJump); if (nextPosition > 0) { if (helper(stones, nextPosition, i)) return true; } } return false; }
http://xiadong.info/2016/09/leetcode-403-frog-jump/
虽然tag里说这是个DP题, 但是我觉得更像个图论题. 每个stone是一个node, 根据能否到达来判断有没有边相连, 最终要判断第一个节点与最后一个节点是否连通.
那么既然是这样, 就有DFS和BFS两派了. 用BFS的话要记录抵达每个node的上一跳可能有多远, 同时要记录一个node有没有访问过, 所以比较复杂.
    bool canCross(vector<int>& stones) {
        return canCrossImpl(stones, 0, 0);
    }
    
    bool canCrossImpl(vector<int>& stones, int index, int lastStep){
        for(int i = index + 1; i < stones.size(); i++){
            if(stones[i] - stones[index] < lastStep - 1) continue;
            if(stones[i] - stones[index] > lastStep + 1) return false;
            if(canCrossImpl(stones, i, stones[i] - stones[index])) return true;
        }
        return index == stones.size() - 1;
    }

X. BFS
http://bookshadow.com/weblog/2016/09/18/leetcode-frog-jump/
利用元组(x, y)表示青蛙跳跃的状态:x表示位置, y表示上一跳的单元数。
初始将(0, 0)加入队列q,利用二维数组v记录元组(x, y)是否被访问过。
循环遍历队列q,根据队头状态扩展队列,直到队列为空。
def canCross(self, stones): """ :type stones: List[int] :rtype: bool """ q = collections.deque() v = collections.defaultdict(lambda : collections.defaultdict(bool)) stoneSet = set(stones) q.append((0, 0)) v[0][0] = True while q: x, y = q.popleft() if x == stones[-1]: return True for z in (y - 1, y, y + 1): if z > 0 and not v[x + z][z] and x + z in stoneSet: v[x + z][z] = True q.append((x + z, z)) return False


由于这道题只是让我们判断青蛙是否能跳到最后一个石头上,并没有让我们返回所有的路径,这样就降低了一些难度

http://www.georgelyu.me/2016/09/18/7/


No comments:

Post a Comment

Labels

GeeksforGeeks (959) Algorithm (811) LeetCode (632) to-do (596) Classic Algorithm (334) Review (330) Classic Interview (299) Dynamic Programming (263) Google Interview (229) LeetCode - Review (224) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (118) Bit Algorithms (110) Cracking Coding Interview (110) Smart Algorithm (109) Math (91) HackerRank (85) Lintcode (83) Binary Search (73) Graph Algorithm (73) Interview Corner (61) Greedy Algorithm (60) List (58) Binary Tree (56) DFS (54) Algorithm Interview (53) Advanced Data Structure (52) Codility (52) ComProGuide (52) LeetCode - Extended (47) USACO (46) Geometry Algorithm (44) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Interval (38) Jobdu (38) Recursive Algorithm (38) Stack (38) String Algorithm (38) Binary Search Tree (37) Knapsack (37) Codeforces (36) Introduction to Algorithms (36) Matrix (36) Must Known (36) Beauty of Programming (35) Sort (35) Array (33) prismoskills (33) Segment Tree (32) Space Optimization (32) Trie (32) Union-Find (32) Backtracking (31) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Data Structure Design (29) Company-Zenefits (28) Microsoft 100 - July (28) to-do-must (28) Random (27) Sliding Window (26) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Queue (22) DFS + Review (21) Hash (21) TopCoder (21) Binary Indexed Trees (20) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Pre-Sort (20) Company-Facebook (19) UVA (19) Probabilities (18) Follow Up (17) Codercareer (16) Company-Uber (16) Game Theory (16) Heap (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Iterator (15) Merge Sort (15) O(N) (15) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Bisection Method (13) Codechef (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) KMP (12) Long Increasing Sequence(LIS) (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Ordered Stack (11) Princeton (11) Tree DP (11) 挑战程序设计竞赛 (11) Binary Search - Bisection (10) Company - Microsoft (10) Company-Airbnb (10) Euclidean GCD (10) Facebook Hacker Cup (10) HackerRank Easy (10) Reverse Thinking (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) X Sum (10) Coin Change (9) Lintcode - Review (9) Mathblog (9) Max-Min Flow (9) Stack Overflow (9) Stock (9) Two Pointers (9) Book Notes (8) Bottom-Up (8) DP-Space Optimization (8) Divide and Conquer (8) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) System Design (8) Tech-Queries (8) Use XOR (8) 穷竭搜索 (8) Algorithm Problem List (7) DFS+BFS (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Linked List (7) Longest Common Subsequence(LCS) (7) Math-Divisible (7) Miscs (7) O(1) Space (7) Probability DP (7) Radix Sort (7) Simulation (7) Suffix Tree (7) Xpost (7) n00tc0d3r (7) 蓝桥杯 (7) Bucket Sort (6) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Level Order Traversal (6) Manacher (6) Minimum Spanning Tree (6) One Pass (6) Programming Pearls (6) Quick Select (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Suffix Array (6) Threaded (6) Time Complexity (6) reddit (6) AI (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Crazyforcode (5) DFS+Cache (5) DP-Multiple Relation (5) DP-Print Solution (5) Dutch Flag (5) Fast Slow Pointers (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Inversion (5) Java (5) Kadane - Extended (5) Kadane’s Algorithm (5) Matrix Chain Multiplication (5) Microsoft Interview (5) Morris Traversal (5) Pruning (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Traversal Once (5) TreeMap (5) jiuzhang (5) to-do-2 (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Anagram (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Company-Amazon (4) Consistent Hash (4) Convex Hull (4) Cycle (4) DP-Include vs Exclude (4) Dijkstra (4) Distributed (4) Eulerian Cycle (4) Flood fill (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) Left and Right Array (4) MinMax (4) Multiple Data Structures (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Pre-Sum (4) Probability (4) Programcreek (4) Quick Sort (4) Spell Checker (4) Stock Maximize (4) Subsets (4) Sudoku (4) Sweep Line (4) Symbol Table (4) TreeSet (4) Triangle (4) Water Jug (4) Word Ladder (4) algnotes (4) fgdsb (4) 最大化最小值 (4) A Star (3) Abbreviation (3) Algorithm - Brain Teaser (3) Algorithm Design (3) Anagrams (3) B Tree (3) Big Data Algorithm (3) Binary Search - Smart (3) Caterpillar Method (3) Coins (3) Company - Groupon (3) Company - Indeed (3) Cumulative Sum (3) DP-Fill by Length (3) DP-Two Variables (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Edit Distance (3) Expression (3) Finite Automata (3) Forward && Backward Scan (3) Github (3) GoLang (3) Include vs Exclude (3) Joseph (3) Jump Game (3) Knapsack-多重背包 (3) LeetCode - Bit (3) LeetCode - TODO (3) Linked List Merge Sort (3) LogN (3) Maze (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Stack - Smart (3) State Machine (3) Streaming Algorithm (3) Subset Sum (3) Subtree (3) Transform Tree (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Search (3) bookkeeping (3) codebytes (3) Activity Selection Problem (2) Advanced Algorithm (2) AnAlgorithmADay (2) Application of Algorithm (2) Array Merge (2) BOJ (2) BT - Path Sum (2) Balanced Binary Search Tree (2) Bellman Ford (2) Binomial Coefficient (2) Bit Mask (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Branch and Bound Method (2) Clock (2) Codesays (2) Company - Baidu (2) Complete Binary Tree (2) DFS+BFS, Flood Fill (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-Output Solution (2) DP-Slide Window Gap (2) DP-i-k-j (2) DP-树形 (2) Distributed Algorithms (2) Divide and Conqure (2) Doubly Linked List (2) GoHired (2) Graham Scan (2) Graph - Bipartite (2) Graph BFS+DFS (2) Graph Coloring (2) Graph-Cut Vertices (2) Hamiltonian Cycle (2) Huffman Tree (2) In-order Traverse (2) Include or Exclude Last Element (2) Information Retrieval (2) Interview - Linkedin (2) Invariant (2) Islands (2) Knuth Shuffle (2) LeetCode - Recursive (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) MST (2) MST-Kruskal (2) Master Theorem (2) Math-Remainder Queue (2) Matrix Power (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Palindromic (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) Shuffle (2) Sieve of Eratosthenes (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Stream (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Word Break (2) Word Graph (2) Word Trie (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - How To (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary Tree Variant (1) Bipartite (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Bug Free Code (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular Buffer (1) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Snapchat (1) Company-Yelp (1) Compression Algorithm (1) Concurrency (1) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS-Matrix (1) DP - Probability (1) DP Fill Diagonal First (1) DP-Difficult (1) DP-End with 0 or 1 (1) DP-Fill Diagonal First (1) DP-Graph (1) DP-Left and Right Array (1) DP-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Optimization (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) Database (1) Detect Negative Cycle (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Duplicate (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (1) Game (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) HOJ (1) Hanoi (1) Hard Algorithm (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Inorder-Reverse Inorder Traverse Simultaneously (1) Interpolation search (1) Interview (1) Interview - Easy (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Kosaraju’s algorithm (1) Kruskal (1) Kruskal MST (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode Diffcult (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Local MinMax (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Median (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Successor (1) Offline Algorithm (1) PAT (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) Probabilistic Data Structure (1) Proof (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Regular Expression (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie + DFS (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) Yahoo Interview (1) ZOJ (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts