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
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;
    }
}

https://discuss.leetcode.com/topic/30999/108ms-easy-to-understand-java-solution
public int nthSuperUglyNumber(int n, int[] primes) {
    int[] ret    = new int[n];
          ret[0] = 1;

    int[] indexes  = new int[primes.length];
   
    for(int i = 1; i < n; i++){
        ret[i] = Integer.MAX_VALUE;
        
        for(int j = 0; j < primes.length; j++){
            ret[i] = Math.min(ret[i], primes[j] * ret[indexes[j]]);
        }
        
        for(int j = 0; j < indexes.length; j++){
            if(ret[i] == primes[j] * ret[indexes[j]]){
                indexes[j]++;
            }
        }
    }
    
    return ret[n - 1];
}

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
http://www.geeksforgeeks.org/generation-n-numbers-given-set-factors/
Given an array of k numbers factor[], the task is to print first n numbers (in ascending order) whose factors are from the given array.
Input  : factor[] = {2, 3, 4, 7} 
         n = 8
Output : 2 3 4 6 7 8 9 10
This problem is mainly an extension of Ugly Number Problem. We create an auxiliary array next[]of size same as factor[] to Keep track of next multiples of factors. In Each iteration, we output the minimum element from next, then increment it by the respective factor. If the minimum value is equal to the previous output value, increment it (to avoid duplicates). Else we print the minimum value.
Time complexity – O(n * k)
Auxiliary Space – O(k)
void generateNumbers(int factor[], int n, int k)
{
    // array of k to store next multiples of
    // given factors
    int next[k] = {0};
    // Prints n numbers 
    int output = 0;  // Next number to print as output
    for (int i=0; i<n; )
    {
        // Find the next smallest multiple
        int toincrement = 0;
        for (int j=0; j<k; j++)
            if (next[j] < next[toincrement])
                toincrement = j;
        // Printing minimum in each iteration
        // print the value if output is not equal to
        // current value(to avoid the duplicates)
        if (output != next[toincrement])
        {
            output = next[toincrement];
            printf("%d ",  next[toincrement]);
            i++;
        }
        // incrementing the current value by the
        // respective factor
        next[toincrement] += factor[toincrement];
    }
}
Read full article from [LeetCode]Super Ugly Number | 书影博客

No comments:

Post a Comment

Labels

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