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

資訊專欄INFORMATION COLUMN

[Leetcode] Ugly Number 丑陋數(shù)

RobinQu / 3374人閱讀

摘要：如果有一個方法能夠順序只生成丑陋數(shù)就好了。仔細(xì)觀察可以發(fā)現(xiàn)，丑陋數(shù)的因子也必定是丑陋數(shù)，它一定是某個丑陋數(shù)乘得到的。不過，我們可以確定的是，小的丑陋數(shù)乘，肯定小于大的丑陋數(shù)乘。

Ugly Number I 
Write a program to check whether a given number is an ugly number.


Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.


Note that 1 is typically treated as an ugly number.

原題鏈接

因式分解法 復(fù)雜度

時間 O(logN) 空間 O(1)

思路

根據(jù)丑陋數(shù)的定義，我們將給定數(shù)除以2、3、5，直到無法整除，也就是除以2、3、5的余數(shù)不再為0時停止。這時如果得到1，說明是所有因子都是2或3或5，如果不是1，則不是丑陋數(shù)。

代碼 
public class Solution {
    public boolean isUgly(int num) {
        if(num == 0){
            return false;
        }
        int rem2 = num % 2;
        int rem3 = num % 3;
        int rem5 = num % 5;
        while(rem2 == 0 || rem3 == 0 || rem5 == 0){
            if(rem2 == 0){
                num = num / 2;
            } else if(rem3 == 0){
                num = num / 3;
            } else {
                num = num / 5;
            }
            rem2 = num % 2;
            rem3 = num % 3;
            rem5 = num % 5;
        }
        return num == 1;
    }
}

簡潔版

for (int i=2; i<6 && num>0; i++)
    while (num % i == 0)
        num /= i;
return num == 1;
Ugly Number II 
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.

原題鏈接

動態(tài)規(guī)劃 復(fù)雜度

時間 O(N) 空間 O(N)

思路

要得到第N個丑陋數(shù)，最直接的想法就是從1開始遞增循環(huán)，直到找到第N個丑陋數(shù)，但是這樣明顯開銷太大，而且我們沒有用到已經(jīng)生成的丑陋數(shù)的信息。如果有一個方法能夠順序只生成丑陋數(shù)就好了。仔細(xì)觀察可以發(fā)現(xiàn)，丑陋數(shù)的因子也必定是丑陋數(shù)，它一定是某個丑陋數(shù)乘2、3、5得到的。但問題在于，小的丑陋數(shù)乘5不一定比大的丑陋數(shù)乘2要小，我們沒法直接使用目前最大的丑陋數(shù)來乘2、3、5順序得到更大的丑陋數(shù)。不過，我們可以確定的是，小的丑陋數(shù)乘2，肯定小于大的丑陋數(shù)乘2。所以我們使用三個指針，分別記錄乘2、3、5得出的目前最大丑陋數(shù)，這樣我們通過比較這三種最大丑陋數(shù)（這里最大是相對于只乘2、只乘3、只乘5三種不同情況下最大的丑陋數(shù)），就得到了所有數(shù)里最大的丑陋數(shù)。

代碼 
public class Solution {
    public int nthUglyNumber(int n) {
        List res = new ArrayList();
        res.add(1);
        int i2 = 0, i3 = 0, i5 = 0;
        while(res.size() < n){
            int m2 = res.get(i2) * 2;
            int m3 = res.get(i3) * 3;
            int m5 = res.get(i5) * 5;
            int min = Math.min(m2, Math.min(m3, m5));
            res.add(min);
            if(min == m2) i2++;
            if(min == m3) i3++;
            if(min == m5) i5++;
        }
        return res.get(res.size()-1);
    }
}

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

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

相關(guān)文章

  • leetcode刷題筆記（2）(python)

    摘要：思路先用將字符串分割，再遍歷，將字符串內(nèi)每個單詞進(jìn)行翻轉(zhuǎn)代碼題意給定一個字符串，將字符串按照翻轉(zhuǎn)，不翻轉(zhuǎn)的規(guī)則進(jìn)行處理。思路先將字符串分段，然后再根據(jù)段落進(jìn)行處理最后將字符串輸出。 344 Reverse String題意：給出一個字符串對字符串進(jìn)行翻轉(zhuǎn)（reverse）思路：直接使用切片函數(shù)進(jìn)行翻轉(zhuǎn)（網(wǎng)上看到的，具體怎么使用有點(diǎn)迷）[::-1]代碼：`class Solution(...

    Guakin_Huang 評論0 收藏0

  • 264. Ugly Number II & 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

  • [LintCode/LeetCode] Super Ugly Number

    摘要：建兩個新數(shù)組，一個存數(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

  • 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

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

    張春雷 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<