264. Ugly Number II & 313. Super Ugly Number

hiyang 發(fā)布于2019-08-16 10:29 / 3010人閱讀

摘要：每次出一個(gè)數(shù)，就把這個(gè)數(shù)的結(jié)果都放進(jìn)去。，指針從個(gè)變成個(gè)。的做法參考還是復(fù)雜度的問題，回頭再看看

264. Ugly Number II

題目鏈接：https://leetcode.com/problems...

dp的方法參考discussion：
https://discuss.leetcode.com/...

dp的subproblem是：dp[i]: i-th ugly number
dp的function是：dp[i] = min(dp[t2] * 2, dp[t3] * 3, dp[t5] * 5)
其中，t2-1, t3-1, t5-1分別為上一個(gè)*2, *3, *5得到的丑數(shù)，所以當(dāng)前dp[t2]*2, dp[t3]*3, dp[t5]*5分別表示當(dāng)前由*2， *3， *5得到的最小丑數(shù)

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

標(biāo)簽還寫了heap，比較明顯的greedy做法，用一個(gè)min heap，top存的是當(dāng)前最小的丑數(shù)，poll出n-1個(gè)數(shù)，最后top就是第n個(gè)丑數(shù)。每次poll出一個(gè)數(shù)，就把這個(gè)數(shù)*2, *3, *5的結(jié)果都放進(jìn)去。這個(gè)復(fù)雜度不太確定，回頭再看看。注意去重，因?yàn)槌?，乘3最后會導(dǎo)致一個(gè)結(jié)果出現(xiàn)多次，還有最后存的結(jié)果可能overflow，所以用long來處理，參考discussion：
https://discuss.leetcode.com/...

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

題目鏈接：https://leetcode.com/problems...

和上一題的方法是一樣的，只不過這里把2，3，5變成了給的primes數(shù)組里的數(shù)。
dp，index指針從3個(gè)變成len(primes)個(gè)。

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：
https://discuss.leetcode.com/...

還是復(fù)雜度的問題，回頭再看看