Thursday, December 3, 2015

LeetCode 313 - Super Ugly Number


Related: LeetCode 263 - Ugly Number
LeetCode 263 + 264 Ugly Number I II
[LeetCode]Super Ugly Number | 书影博客
Write a program to find the nth super ugly number.
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.

题目大意:

编写程序寻找第n个"超级丑陋数"
超级丑陋数是指只包含给定的k个质因子的正数。例如,给定长度为4的质数序列primes = [2, 7, 13, 19],前12个超级丑陋数序列为:[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]
注意:
(1) 1 被认为是超级丑陋数,无论给定怎样的质数列表.
(2) 给定的质数列表以升序排列.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.

https://leetcode.com/discuss/81411/java-three-methods-23ms-58ms-with-heap-performance-explained
https://discuss.leetcode.com/topic/30999/108ms-easy-to-understand-java-solution
public int nthSuperUglyNumber(int n, int[] primes) {
    int [] res = new int[n];
    res[0] = 1;
    int [] cur = new int[primes.length];
    
    for(int i = 1; i < n; i++){
        res[i] = Integer.MAX_VALUE;
        for(int j = 0; j < primes.length; j++){
            if (primes[j] * res[cur[j]] == res[i-1]) {
                cur[j]++;
            }
            res[i] = Math.min(res[i], primes[j]*res[cur[j]]);
        }
    }
    return res[n-1];
}

Basic idea is same as ugly number II, new ugly number is generated by multiplying a prime with previous generated ugly number. One catch is need to remove duplicate
Let's start with the common solution from ugly number II 36 ms, Theoretically O(kN)
the time complexity would be O(m*n) here where m stands for the length of primes.
public int nthSuperUglyNumberI(int n, int[] primes) {
    int[] ugly = new int[n];
    int[] idx = new int[primes.length];

    ugly[0] = 1;
    for (int i = 1; i < n; i++) {
        //find next
        ugly[i] = Integer.MAX_VALUE;
        for (int j = 0; j < primes.length; j++)
            ugly[i] = Math.min(ugly[i], primes[j] * ugly[idx[j]]);
        
        //slip duplicate
        for (int j = 0; j < primes.length; j++) {
            while (primes[j] * ugly[idx[j]] <= ugly[i]) idx[j]++;
        }
    }

    return ugly[n - 1];
}
If you look at the above solution, it has redundant multiplication can be avoided, and also two for loops can be consolidated into one. This trade-off space for speed. 23 ms, Theoretically O(kN)
public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ugly = new int[n];
        int[] idx = new int[primes.length];
        int[] val = new int[primes.length];
        Arrays.fill(val, 1);

        int next = 1;
        for (int i = 0; i < n; i++) {
            ugly[i] = next;
            
            next = Integer.MAX_VALUE;
            for (int j = 0; j < primes.length; j++) {
                //skip duplicate and avoid extra multiplication
                if (val[j] == ugly[i]) val[j] = ugly[idx[j]++] * primes[j];
                //find next ugly number
                next = Math.min(next, val[j]);
            }
        }

        return ugly[n - 1];
    }
Can we do better? Theoretically yes, by keep the one candidates for each prime in a heap, it can improve the theoretical bound to O( log(k)N ), but in reality it's 58 ms. I think it's the result of using higher level object instead of primitive. Can be improved by writing an index heap (http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html)
public int nthSuperUglyNumberHeap(int n, int[] primes) {
    int[] ugly = new int[n];

    PriorityQueue<Num> pq = new PriorityQueue<>();
    for (int i = 0; i < primes.length; i++) pq.add(new Num(primes[i], 1, primes[i]));
    ugly[0] = 1;

    for (int i = 1; i < n; i++) {
        ugly[i] = pq.peek().val;
        while (pq.peek().val == ugly[i]) {
            Num nxt = pq.poll();
            pq.add(new Num(nxt.p * ugly[nxt.idx], nxt.idx + 1, nxt.p));
        }
    }

    return ugly[n - 1];
}

private class Num implements Comparable<Num> {
    int val;
    int idx;
    int p;

    public Num(int val, int idx, int p) {
        this.val = val;
        this.idx = idx;
        this.p = p;
    }

    @Override
    public int compareTo(Num that) {
        return this.val - that.val;
    }
}

http://www.cnblogs.com/Liok3187/p/5016076.html
和Ugly Number II一样的思路。
动态规划,ugly number肯定是之前的ugly number乘以primes中的其中一个数得到的。
结果存在dp数组中,每一个dp中的数都要乘以primes中的数,寻找所有的结果,也就是说primes中的每一个数都需要一个变量记录位置。
举例来说primes : [2, 5, 7]。
一开始2, 5, 7都指向0的位置。
每一轮循环都用2, 5, 7与当前位置的数相乘,把最小的放进dp数组中。

 1 public static int nthSuperUglyNumber(int n, int[] primes) {
 2     int[] dp = new int[n + 1], prime = new int[primes.length];
 3     int dpIndex = 1, minIndex = -1;
 4     dp[0] = 1;
 5     while(dpIndex <= n){
 6         int min = Integer.MAX_VALUE;
 7         for(int i = 0; i < primes.length; i++){
 8             int tmp = dp[prime[i]] * primes[i];
 9             if(tmp < min){
10                 min = tmp;
11                 minIndex = i;
12             }
13         }
14         prime[minIndex]++;
15         if(min != dp[dpIndex - 1]){
16             dp[dpIndex] = min;
17             dpIndex++;
18         }
19     }
20     return dp[n - 1];
21 }
http://leetcode0.blogspot.com/2015/12/super-ugly-number_10.html
动态规划,ugly number一定是由一个较小的ugly number乘以2,3或5得到的。
先开一个数组记录所有的ugly number。
然后开一个变量数组A,一开始都是零,指向数组的第0位。    A[i]是ugly number的index,
A[i] * primes[i] > current ugly number

每一次取Min(A[i] * primes[i]),找到这个数之后,对应的A[i]加一,指向数组的下一位。
    public int nthSuperUglyNumber(int n, int[] primes) {
        int res[]  = new int[n];
        int A[] = new int[primes.length];// the index that A[j] * prime[j] > current Ugly number
        res[0] = 1;
        for(int i =1; i<n;i++){
            int lastUgly = res[i-1];
            int minProduct = Integer.MAX_VALUE;// one possible value
            for(int j = 0 ; j< primes.length; j++){// for each prime number
                while(res[A[j]] * primes[j] <= lastUgly)// update its preceding index
                    A[j]++;
                if(res[A[j]] * primes[j] < minProduct)// find the min product
                    minProduct = res[A[j]] * primes[j];
            }
            res[i] = minProduct;
        }
        return res[n-1];

    }
http://my.oschina.net/Tsybius2014/blog/547766

找出第n个超级丑数,思路与找出第n个丑数是一样的。区别仅在与找出第n个丑数时,用三个数字记录中间变量,而在找第n个超级丑数时,用一个数组记录。
    public int nthSuperUglyNumber(int n, int[] primes) {
         
        int[] superUglyNumbers = new int[n];
        superUglyNumbers[0] = 1;
        int[] idxPrimes = new int[primes.length];
        for (int i = 0; i < idxPrimes.length; i++) {
            idxPrimes[i] = 0;
        }
         
        int counter = 1;
        while (counter < n) {
             
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < primes.length; i++) {
                int temp = superUglyNumbers[idxPrimes[i]] * primes[i];
                min = min < temp ? min : temp;
            }
            for (int i = 0; i < primes.length; i++) {
                if (min == superUglyNumbers[idxPrimes[i]] * primes[i]) {
                    idxPrimes[i]++;
                }
            }
             
            superUglyNumbers[counter] = min;
            counter++;
        }
         
        return superUglyNumbers[n - 1];
    }
http://bookshadow.com/weblog/2015/12/03/leetcode-super-ugly-number/
时间复杂度O(n * k),k为primes的长度

public int nthSuperUglyNumber(int n, int[] primes) { int size = primes.length; int q[] = new int[n]; int idxes[] = new int[size]; int vals[] = new int[size]; q[0] = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < size; j++) { vals[j] = q[idxes[j]] * primes[j]; } int min = findMin(vals); q[i] = min; for (int j = 0; j < size; j++) { if (vals[j] == min) { idxes[j] += 1; } } } return q[n - 1]; } public int findMin(int[] nums) { int min = nums[0]; for (int i = 1; i < nums.length; i++) { min = Math.min(min, nums[i]); } return min;

X. 使用堆(优先队列)O(nlogk)

维护一个小顶堆,弹出元素时,将其乘以primes中的每一个元素然后加入堆
https://discuss.leetcode.com/topic/30946/using-min-heap-accepted-java-and-python-code
The idea is similar to 264 Ugly Number II. The insight is that each new ugly number is generated from the previous ugly number by multiplying one of the prime. Thus we can maintain a pointer for each prime which indicates the current position of the generated ugly number list. Then there is a new ugly number from each prime, then we find the minimum one from them. Naturally the minimum one can be found by min-heap.
public int nthSuperUglyNumber(int n, int[] primes) {
 Comparator<Number> comparator = new NumberCompare();
 PriorityQueue<Number> queue = 
            new PriorityQueue<Number>(primes.length, comparator);
 for(int i = 0; i < primes.length; i ++) 
  queue.add(new Number(primes[i], 0, primes[i]));
 int[] uglyNums = new int[n];
 uglyNums[0] = 1;
 for(int i = 1; i < n; i++){
  Number min = queue.peek();
  uglyNums[i] = min.un;
  while(queue.peek().un == min.un){
   Number tmp = queue.poll();
   queue.add(new Number(uglyNums[tmp.pos + 1] * tmp.prime, tmp.pos+1, tmp.prime)); 
  }
 }
 
 return uglyNums[n-1];
}

public class Number{
 int un;
 int pos;
 int prime;
 Number(int un, int pos, int prime){
  this.un = un;
  this.pos = pos;
  this.prime = prime;
 }
}

public class NumberCompare implements Comparator<Number>{

 @Override
 public int compare(Number x, Number y) {
  // TODO Auto-generated method stub
  if (x.un > y.un)
   return 1;
  else if (x.un < y.un)
   return -1;
  else
   return 0;
 }
}


public int nthSuperUglyNumber(int n, int[] primes){
    PriorityQueue<Number> queue =
            new PriorityQueue<Number>();
    Set<Integer> uglySet = new HashSet<Integer>();
    for(int i = 0; i < primes.length; i ++) {
        queue.add(new Number(primes[i], 0, primes[i]));
        uglySet.add(primes[i]);
    }
    int[] uglyNums = new int[n];
    uglyNums[0] = 1;
    for(int i = 1; i < n; i++){
        Number min = queue.poll();
        uglyNums[i] = min.un;
        int j = min.pos+1;
        int newNum = min.prime * uglyNums[j];
        while (uglySet.contains(newNum))
             newNum = min.prime * uglyNums[++j];
        queue.add(new Number(newNum, j, min.prime));
        uglySet.add(newNum);
    }
    return uglyNums[n-1];
}

public class Number implements Comparable<Number>{
    int un;
    int pos;
    int prime;
    Number(int un, int pos, int prime){
        this.un = un;
        this.pos = pos;
        this.prime = prime;
    }
    @Override
    public int compareTo(Number x) {
        // TODO Auto-generated method stub
        return this.un > x.un ? 1 : -1;
    }
}
Are you sure this is nlog(k)? Your outer loop runs n times and your inner loop may run multiple times each time, causing several log(k) instead of just one.
Yes, you are right Stefan. The number of log(k) in the inner loop depends on the duplicates of the numbers when generating the kth number. Previously I thought the duplicate number would be negligible. But it turns out not. I checked that there are about 20M duplicates when n = 500K.
I then made this change: use a hashset to store all the used numbers in the heap, and also add the one which has not appeared in the hashset.
public int nthSuperUglyNumber(int n, int[] primes) {
    Comparator<Number> comparator = new NumberCompare();
    PriorityQueue<Number> queue =
            new PriorityQueue<Number>(primes.length, comparator);
    for(int i = 0; i < primes.length; i ++)
        queue.add(new Number(primes[i], 0, primes[i]));
    int[] uglyNums = new int[n];
    uglyNums[0] = 1;
    for(int i = 1; i < n; i++){
        Number min = queue.peek();
        uglyNums[i] = min.un;
        while(queue.peek().un == min.un){
            Number tmp = queue.poll();
            queue.add(new Number(uglyNums[tmp.pos + 1] * tmp.prime, tmp.pos+1, tmp.prime));
        }
    }

    return uglyNums[n-1];
}
https://www.hrwhisper.me/leetcode-super-ugly-number/
和 leetcode Ugly Number  II 思路一样,要使得super ugly number 不漏掉,那么用每个因子去乘第一个,当前因子乘积是最小后,乘以下一个…..以此类推。
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ugly_number = new int[n];
        ugly_number[0] = 1;
        PriorityQueue<Node> q = new PriorityQueue<Node>();
        for (int i = 0; i < primes.length; i++)
            q.add(new Node(0, primes[i], primes[i]));
        for (int i = 1; i < n; i++) {
            Node cur = q.peek();
            ugly_number[i] = cur.val;
            do {
                cur = q.poll();
                cur.val = ugly_number[++cur.index] * cur.prime;
                q.add(cur);
            } while (!q.isEmpty() && q.peek().val == ugly_number[i]);
        }
        return ugly_number[n - 1];
    }
}
class Node implements Comparable<Node> {
    int index;
    int val;
    int prime;
    Node(int index, int val, int prime) {
        this.val = val;
        this.index = index;
        this.prime = prime;
    } 
    public int compareTo(Node x) {
        return this.val - x.val ;
    }
}
X. You get faster performance for custom heap, if use PriorityQueue, the performance is much more poor
https://discuss.leetcode.com/topic/35149/java-31ms-o-nlgk-solution-with-heap
public int nthSuperUglyNumber(int n, int[] primes){
    int[] index = new int[1000];
    int[] res = new int[n];
    int[] heap = new int[primes.length];
    for(int i = 0;i<primes.length; i++)heap[i] = primes[i];
    res[0] = 1;
    for(int i = 1; i<n;)
    {
        if(res[i-1] != heap[0]){         
         res[i] = heap[0];
         System.out.print(res[i]+" ");
         i++;
        }
        updateHeap(heap,primes,index,res);
    }
    return res[n-1];
}
public void heapify(int[] heap, int[] primes, int i){
    int index = i;
    int left = 2*i+1; int right = left+1;
    if(heap.length>left && heap[i] > heap[left]) index = left;
    if(heap.length>right && heap[index] > heap[right]) index = right;
    if(i!=index){
        int temp = heap[i];
        heap[i] = heap[index];
        heap[index] = temp;
        int tempPri = primes[i];
        primes[i] = primes[index];
        primes[index] = tempPri;
        heapify(heap,primes,index);
    }
}
public void updateHeap(int[] heap, int[] primes, int[] index, int[] res)
{
    index[primes[0]]++;
    heap[0] = res[index[primes[0]]] * primes[0];
    heapify(heap,primes,0);
}
https://discuss.leetcode.com/topic/31957/heap-is-slower-than-array-possible-explanation
Read full article from [LeetCode]Super Ugly Number | 书影博客

No comments:

Post a Comment

Labels

GeeksforGeeks (976) Algorithm (811) LeetCode (663) to-do (600) Review (373) Classic Algorithm (334) Classic Interview (298) Dynamic Programming (263) LeetCode - Review (235) Google Interview (233) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (119) Bit Algorithms (111) Cracking Coding Interview (110) Smart Algorithm (110) Math (91) HackerRank (85) Lintcode (83) Binary Search (73) Graph Algorithm (73) Greedy Algorithm (61) Interview Corner (61) Binary Tree (58) List (58) DFS (56) Algorithm Interview (53) Advanced Data Structure (52) Codility (52) ComProGuide (52) LeetCode - Extended (47) USACO (46) Geometry Algorithm (45) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Jobdu (39) Stack (39) Binary Search Tree (38) Interval (38) Recursive Algorithm (38) String Algorithm (38) Knapsack (37) Codeforces (36) Introduction to Algorithms (36) Matrix (36) Must Known (36) Beauty of Programming (35) Sort (35) Space Optimization (34) Array (33) Trie (33) prismoskills (33) Backtracking (32) Segment Tree (32) Union-Find (32) 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 (27) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Hash (22) Queue (22) Binary Indexed Trees (21) DFS + Review (21) TopCoder (21) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Pre-Sort (20) Company-Facebook (19) UVA (19) Probabilities (18) Follow Up (17) Merge Sort (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) O(N) (15) Bisection Method (14) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Codechef (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) KMP (12) Long Increasing Sequence(LIS) (12) Modify Tree (12) Ordered Stack (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) 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) Divide and Conquer (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) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) Quick Sort (8) Suffix Tree (8) System Design (8) Tech-Queries (8) Time Complexity (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) 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) Kadane’s Algorithm (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) 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) 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) Sweep Line (5) Traversal Once (5) TreeMap (5) jiuzhang (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) Spell Checker (4) Stock Maximize (4) Subsets (4) Sudoku (4) Symbol Table (4) TreeSet (4) Triangle (4) Water Jug (4) Word Ladder (4) algnotes (4) fgdsb (4) to-do-2 (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) Master Theorem (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) 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) Parent-Only Tree (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