264. Ugly NumberII & 313. Super Ugly Number

Lionad-Morotar 發布于2019-08-14 14:06 / 3352人閱讀

摘要：題目解答這個問題最主要的就是如果按順序找出那么我們如果能想到把以為因子的這些分成三個然后在每次輸出時取里最小的那個數輸出就可以解決了。

264 Ugly NumberII
題目：
Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

解答：
這個問題最主要的就是如果按順序找出ugly number, 那么我們如果能想到把以2, 3, 5為因子的這些ugly number分成三個list, 然后在每次輸出時取list里最小的那個數輸出就可以解決了。代碼如下：

public class Solution {
    // (1) 1*2, 2*2, 3*2, 4*2,...
    // (2) 1*3, 2*3, 3*3, 4*3,...
    // (3) 1*5, 2*5, 3*5, 4*5,...
    class Num {
        int index, factor;
        public Num(int index, int factor) {
            this.index = index;
            this.factor = factor;
        }
    }

    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        Num l2 = new Num(1, 2);
        Num l3 = new Num(1, 3);
        Num l5 = new Num(1, 5);
        for (int i = 1; i < n; i++) {
            int min = Math.min(l2.factor, Math.min(l3.factor, l5.factor));
            ugly[i] = min;
            if (l2.factor == min) {
                l2.factor = ugly[l2.index++] * 2;
            }
            if (l3.factor == min) {
                l3.factor = ugly[l3.index++] * 3;
            }
            if (l5.factor == min) {
                l5.factor = ugly[l5.index++] * 5;
            }
        }
        return ugly[n - 1];
    }
}

其實這道題還有一個更in general的解法，跟super ugly number可以用一樣的解法：

public int nthUglyNumber(int n) {
    int[] primes = {2, 3, 5};
    int[] ugly = new int[n];
    int[] index = new int[primes.length];
    
    ugly[0] = 1;
    for (int i = 1; i < n; i++) {
        ugly[i] = Integer.MAX_VALUE;
        for (int j = 0; j < primes.length; j++) {
            //從每個prime現在乘到的數開始繼續往下乘
            ugly[i] = Math.min(ugly[i], primes[j] * ugly[index[j]]);
        }
        
        for (int j = 0; j < primes.length; j++) {
            while (primes[j] * ugly[index[j]] == ugly[i]) {
                index[j]++;
            }
        }
    }
    return ugly[n - 1];
}

313 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.

解答：

public int nthSuperUglyNumber(int n, int[] primes) {
    int[] ugly = new int[n];
    int[] index = new int[primes.length];
    
    ugly[0] = 1;
    for (int i = 1; i < n; i++) {
        ugly[i] = Integer.MAX_VALUE;
        //找到最小的值
        for (int j = 0; j < primes.length; j++) {
            ugly[i] = Math.min(ugly[i], primes[j] * ugly[index[j]]);
        }
        //去重
        for (int j = 0; j < primes.length; j++) {
            while (ugly[i] == primes[j] * ugly[index[j]]) {
                index[j]++;
            }
        }
    }
    return ugly[n - 1];
}

GPU云服務器云服務器 Ugly NumberII V313 super

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

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

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

摘要：每次出一個數，就把這個數的結果都放進去。，指針從個變成個。的做法參考還是復雜度的問題，回頭再看看 264. Ugly Number II 題目鏈接：https://leetcode.com/problems... dp的方法參考discussion：https://discuss.leetcode.com/... dp的subproblem是：dp[i]: i-th ugly numb...

hiyang 2019-08-16 10:29 評論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