264. Ugly Number II & 313. Super Ugly Number

hiyang 發布于2019-08-16 10:29 / 2937人閱讀

摘要：每次出一個數，就把這個數的結果都放進去。，指針從個變成個。的做法參考還是復雜度的問題，回頭再看看

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分別為上一個*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：
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數組里的數。
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：
https://discuss.leetcode.com/...

還是復雜度的問題，回頭再看看

云服務器 GPU云服務器 Ugly number number用法 number型數據

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69877.html

264. Ugly NumberII &amp; 313. Super Ugly Number

摘要：題目解答這個問題最主要的就是如果按順序找出那么我們如果能想到把以為因子的這些分成三個然后在每次輸出時取里最小的那個數輸出就可以解決了。 264 Ugly NumberII題目：Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only i...

Lionad-Morotar 2019-08-14 14:06 評論0 收藏0
leetcode263,264,313 ugly numbers

摘要：這題可以使用暴力遍歷法，從開始，對每一個數都進行判斷，直到找到第個丑數為止。優先隊列可以很好的滿足該情況。因此每個素數持有的信息包括當前對應的丑數的下標。前言這一篇博客把ugly numbers系列的題目做一個整理。這三道題正好是一個思路的循序漸進，所以放在一篇博客當中。 Ugly Number Write a program to check whether a given nu...

everfly 2019-08-16 11:02 評論0 收藏0
Leetcode[313] Super Ugly Number

摘要：滾動求最大值復雜度考慮一個，的值是下一個可能的替補值。思路數組中保存的是之前保留到的值，因為下一個可能的值是和之前的值的倍數關系。 Leetcode[313] Super Ugly Number Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whos...

Aklman 2019-08-16 10:27 評論0 收藏0
leetcode-313-Super Ugly Number

摘要：題意找出以某些數為公因數的遞增排序的第個數條件維護了的元素的相乘因素的。由于是最小值，所以每次保留最小的。問題轉化，多次迭代，變成，處理對象變了。不重復的思想找出重復計算的地方，找出不重復計算的方法，用極值約束，加以記錄。題意：找出以某些數為公因數的遞增排序的第n個數條件：indexes 維護了 primes的元素的相乘因素（uglies）的index。思路：每次從 prim...

張春雷 2019-07-30 17:35 評論0 收藏0
[LintCode/LeetCode] Super Ugly Number

摘要：建兩個新數組，一個存數，一個存。數組中所有元素初值都是。實現的過程是，一個循環里包含兩個子循環。兩個子循環的作用分別是，遍歷數組與相乘找到最小乘積存入再遍歷一次數組與的乘積，結果與相同的，就將加，即跳過這個結果相同結果只存一次。 Problem Write a program to find the nth super ugly number. Super ugly numbers a...

wuyumin 2019-08-14 15:20 評論0 收藏0