leetcode263,264,313 ugly numbers

everfly 發布于2019-08-16 11:02 / 2314人閱讀

摘要：這題可以使用暴力遍歷法，從開始，對每一個數都進行判斷，直到找到第個丑數為止。優先隊列可以很好的滿足該情況。因此每個素數持有的信息包括當前對應的丑數的下標。

前言

這一篇博客把ugly numbers系列的題目做一個整理。這三道題正好是一個思路的循序漸進，所以放在一篇博客當中。

Ugly Number

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.

丑數是指只包含2,3,5質因數的數。因此6,8是丑數因為6=2*3,8=2*2*2，而14不是丑數因為14包含質因數7?，F在寫一個方法判斷一個數字是否是丑數。

這題只需要將所有的2，3，5質數消去之后，余下的質數是不是1來進行判斷。代碼如下：

    public boolean isUgly(int num) {
        if(num <= 0) return false;
        while(num % 2 == 0) num /= 2;
        while(num % 5 == 0) num /= 5;
        while(num % 3 == 0) num /= 3;
        return num == 1;
    }

264. 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, and n does not exceed 1690.

這道題目在上一題定義的基礎上，要找到第n個丑數。

這題可以使用暴力遍歷法，從1開始，對每一個數都進行判斷，直到找到第n個丑數為止。但是這樣的方法效率很差。所以需要尋找一下這些數之間的規律，從而找到更好的解決方法。

這里運用了Dynamic Programming的編程思想來解決。現在我們可以將丑數完整的歸入以下三類：

全部丑數：  1,2,3,4,5,6,8...
包含丑數2：1*2,2*2,3*2,4*2,5*2,6*2,8*2...
包含丑數3：1*3,2*3,3*3,4*3,5*3,6*3,8*3...
包含丑數5：1*5,2*5,3*5,4*5,5*5,6*5,7*5...

可以看到，每一個丑數子列上，第i位上的值等于全部丑數的第i個丑數*素數。我們只需要像歸并算法中的合并方法那樣，將三個子列按照從小到大的情況合并成一個序列即可。

我們從基礎情況開始推理，那么每一步的結果如下；

第0步：

全部丑數：1
包含丑數2：2
包含丑數3：3
包含丑數5：5

此時比較三個子序列，得出最小值為2，則更新全部丑數序列，并且更新包含丑數2的子序列，如下：

第1步

全部丑數：1,2
包含丑數2：2,4(2*2)
包含丑數3：3,
包含丑數5：5,

再次比較三個子序列，得出最小值為3，更新方法同上，結果如下：
第2步

全部丑數：1,2,3
包含丑數2：2,4
包含丑數3：3,6(2*3)
包含丑數5：5

按照如上方法我們就可以得出第n個丑數的值。代碼如下

    public int nthUglyNumber(int n) {
        int idx1 = 0, idx2 = 0, idx3 = 0;
        int[] result = new int[n];
        result[0] = 1;
        for(int i = 1 ; i
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.
(4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.
這一題和上一題的變化相比，基本素數從[2,3,5]變成了任意數量的有序素數構成的數組。其實本質上思路還是一樣的，我們只需要新建一個數組來存放當前子序列丑數對應的所有丑數的下標就可以了。代碼如下：
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] index = new int[primes.length];
        int[] uglyNumbers = new int[primes.length];
        System.arraycopy(primes, 0, uglyNumbers, 0, primes.length);
        
        int[] result = new int[n];
        result[0] = 1;
        for(int i = 1 ; i
當然，這道題也可以利用特殊的數據結構來完成。優先隊列可以很好的滿足該情況。我們先將題目中提供的所有素數輸入到優先隊列中，相當于存入了所有的子丑數列的第一個元素。因此每個素數持有的信息包括當前對應的丑數的下標。之后我們可以將比較的任務交給優先隊列的完成，我們只需從中提取最小的那個數，加到結果集中，同時別忘了更新各個子序列從而消去出現重復值的情況。
代碼如下：
    public int nthSuperUglyNumberHeap(int n, int[] primes) {
        int[] ugly = new int[n];

        PriorityQueue pq = new PriorityQueue<>();
        for (int i = 0; i < primes.length; i++) pq.add(new Num(primes[i], 1, primes[i]));
        ugly[0] = 1;

        for (int i = 1; i < n; i++) {
            ugly[i] = pq.peek().val;
            while (pq.peek().val == ugly[i]) {
                Num nxt = pq.poll();
                pq.add(new Num(nxt.p * ugly[nxt.idx], nxt.idx + 1, nxt.p));
            }
        }

        return ugly[n - 1];
    }

    private class Num implements Comparable {
        int val;
        int idx;
        int p;

        public Num(int val, int idx, int p) {
            this.val = val;
            this.idx = idx;
            this.p = p;
        }

        @Override
        public int compareTo(Num that) {
            return this.val - that.val;
        }
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 Ugly V313 Leetcod LeetCode

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

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

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
264. Ugly NumberII & 313. Super Ugly Number

摘要：題目解答這個問題最主要的就是如果按順序找出那么我們如果能想到把以為因子的這些分成三個然后在每次輸出時取里最小的那個數輸出就可以解決了。 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 2019-08-14 14:06 評論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
leetcode刷題筆記（2）(python)

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

Guakin_Huang 2019-07-30 14:44 評論0 收藏0