动态规划 - 49.丑数

1.小根堆
方法一：堆
首先我们可以发现，一个丑数最基本的特征就是被2，或者被3，或者被5整除，我们逆向思维考虑的话，是不是一个数2，或者3，或者*5，就是一个丑数呢？那么这个数是是什么呢？那么这个限制就是因数只存在2，3，5，也就是这个数本身就是丑数！
所以丑数 *2，*3 或者 *5，也是丑数。
根据这个思想，我们已经将问题解决了一半。现在我们就需要想怎么样存储了。
首先它是一个由小到大的顺序，根据这个特性，我们很容易想到的是优先级队列，按大小顺序可以出队。
我们将丑数从先存储进小根堆中，然后出队，添加到数组中，那么此时就可以按顺序排列好的顺序填入数组了。
还有个问题就是去重问题了。
因为 *2 又 *3，再 *5，按丑数的顺序进行计算，是一定会计算出重复的数字的。
所以我们还需要一个去重的容器，HashSet，辅助我们添加丑数。

class Ugly {
  public int[] nums = new int[1690];
  Ugly() {
  //辅助去重
    HashSet<Long> seen = new HashSet();
    //小根堆
    PriorityQueue<Long> heap = new PriorityQueue<Long>();
    //把丑数先添加到HashSet中，然后每添加一个丑数，先比较在HashSet中是否重复了，如果重复直接丢弃即可。
    seen.add(1L);
    //去重之后再添加到小根堆中
    heap.add(1L);

    long currUgly, newUgly;
    int[] primes = new int[]{2, 3, 5};
    for(int i = 0; i < 1690; ++i) {
      currUgly = heap.poll();
      nums[i] = (int)currUgly;
      for(int j : primes) {
        newUgly = currUgly * j;
        if (!seen.contains(newUgly)) {
          seen.add(newUgly);
          heap.add(newUgly);
        }
      }
    }
  }
}

class Solution {
  public static Ugly u = new Ugly();
  public int nthUglyNumber(int n) {
    return u.nums[n - 1];
  }
}

2.动态规划（三指针法）。

LeetCode