国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Leetcode[313] Super Ugly Number

Aklman / 2235人閱讀

摘要：滾動求最大值復雜度考慮一個，的值是下一個可能的替補值。思路數(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 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.
滾動求最大值

復雜度
考慮一個index，i
primes[index] * res[index[i]]的值是下一個可能的替補值。

思路
int[] res數(shù)組中保存的是之前保留到的值，因為下一個可能的值是primes[i]和之前的值的倍數(shù)關(guān)系。

代碼

public int nthSuperUglyNumber(int n, int[] primes) {
    int[] res = new int[n];
    res[0] = 1;
    int[] index = new int[primes.length];
    for(int i = 1; i < n; i ++) {
        res[i] = Integer.MAX_VALUE;
        for(int j = 0; j < primes.length; j ++) {
            res[i] = Math.min(res[i], primes[j] * res[index[j]]);
        }
        //
        for(int j = 0; j < primes.length; j ++) {
            if(primes[j] * res[index[j]] == res[i]) {
                index[j] ++;
            }
        }
    }
    return res[n - 1];
}

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

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/69837.html

相關(guān)文章

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

    摘要：每次出一個數(shù)，就把這個數(shù)的結(jié)果都放進去。，指針從個變成個。的做法參考還是復雜度的問題，回頭再看看 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

  • leetcode-313-Super Ugly Number

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

    張春雷 評論0 收藏0

  • leetcode263,264,313 ugly numbers

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

    everfly 評論0 收藏0

  • 264. Ugly NumberII & 313. Super Ugly Number

    摘要：題目解答這個問題最主要的就是如果按順序找出那么我們?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 i...

    Lionad-Morotar 評論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元查看
<