成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

264. Ugly NumberII & 313. Super Ugly Number

Lionad-Morotar / 3361人閱讀

摘要：題目解答這個問題最主要的就是如果按順序找出那么我們?nèi)绻芟氲桨岩詾橐蜃拥倪@些分成三個然后在每次輸出時取里最小的那個數(shù)輸出就可以解決了。

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, 那么我們?nèi)绻芟氲桨岩?, 3, 5為因子的這些ugly number分成三個list, 然后在每次輸出時取list里最小的那個數(shù)輸出就可以解決了。代碼如下：

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現(xiàn)在乘到的數(shù)開始繼續(xù)往下乘
            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];
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64811.html

相關(guān)文章

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

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

    hiyang 評論0 收藏0

  • leetcode263,264,313 ugly numbers

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

    everfly 評論0 收藏0

  • Leetcode[313] Super Ugly Number

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

    Aklman 評論0 收藏0

  • leetcode-313-Super Ugly Number

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

    張春雷 評論0 收藏0

  • [LintCode/LeetCode] Super Ugly Number

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

    wuyumin 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<