264. Ugly Number II
题目链接：
dp的方法参考discussion：
dp的subproblem是：dp[i]: i-th ugly number
dp[i] = min(dp[t2] * 2, dp[t3] * 3, dp[t5] * 5)其中，t2-1, t3-1, t5-1分别为上一个*2, *3, *5得到的丑数，所以当前dp[t2]*2, dp[t3]*3, dp[t5]*5分别表示当前由*2， *3， *5得到的最小丑数 public class Solution { public int nthUglyNumber(int n) { if(n == 0) return 0; if(n == 1) return 1; int[] dp = new int[n]; dp[0] = 1; int t2 = 0, t3 = 0, t5 = 0; for(int i = 1; i < n; i++) { dp[i] = Math.min(Math.min(dp[t2]*2, dp[t3]*3), dp[t5]*5); if(dp[i] == dp[t2]*2) t2++; if(dp[i] == dp[t3]*3) t3++; if(dp[i] == dp[t5]*5) t5++; } return dp[n-1]; }} 标签还写了heap，比较明显的greedy做法，用一个min heap，top存的是当前最小的丑数，poll出n-1个数，最后top就是第n个丑数。每次poll出一个数，就把这个数*2, *3, *5的结果都放进去。这个复杂度不太确定，回头再看看。注意去重，因为乘2，乘3最后会导致一个结果出现多次，还有最后存的结果可能overflow，所以用long来处理，参考discussion：
public class Solution { public int nthUglyNumber(int n) { if(n == 0) return 0; if(n == 1) return 1; PriorityQueue minHeap = new PriorityQueue(); minHeap.offer(1L); for(int i = 1; i < n; i++) { long cur = minHeap.poll(); // remove duplication while(!minHeap.isEmpty() && minHeap.peek() == cur) minHeap.poll(); minHeap.add(cur*2); minHeap.add(cur*3); minHeap.add(cur*5); } return minHeap.poll().intValue(); }} 313. Super Ugly Number
题目链接：
和上一题的方法是一样的，只不过这里把2，3，5变成了给的primes数组里的数。
dp，index指针从3个变成len(primes)个。public class Solution { public int nthSuperUglyNumber(int n, int[] primes) { if(n == 0) return 0; if(n == 1) return 1; // dp[i]: i-th ugly number int[] dp = new int[n]; int m = primes.length; // index[i]: ugly number producted by primes[i] int[] index = new int[m]; dp[0] = 1; for(int i = 1; i < n; i++) { dp[i] = Integer.MAX_VALUE; for(int j = 0; j < m; j++) dp[i] = Math.min(dp[i], primes[j]*dp[index[j]]); // update index points for(int j = 0; j < m; j++) { if(dp[i] == dp[index[j]] * primes[j]) index[j]++; } } return dp[n-1]; }} heap+dp的做法参考discussion：
还是复杂度的问题，回头再看看