[Leetcode] Ugly Number 丑陋數

RobinQu 發布于2019-08-14 16:09 / 3361人閱讀

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

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.

原題鏈接

因式分解法 復雜度

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

思路

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

代碼

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.

原題鏈接

動態規劃 復雜度

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

思路

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

代碼

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);
    }
}

GPU云服務器云服務器 Ugly LeetCode LeetCode_String leetcode_35_SearchIn

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

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

leetcode刷題筆記（2）(python)

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

Guakin_Huang 2019-07-30 14:44 評論0 收藏0
264. Ugly Number II & 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
[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
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

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

張春雷 2019-07-30 17:35 評論0 收藏0