leetcode263,264,313 ugly numbers

everfly 发布于2019-08-16 11:02 / 2246人阅读

摘要：这题可以使用暴力遍历法，从开始，对每一个数都进行判断，直到找到第个丑数为止。优先队列可以很好的满足该情况。因此每个素数持有的信息包括当前对应的丑数的下标。

前言

这一篇博客把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。现在写一个方法判断一个数字是否是丑数。

这题只需要将所有的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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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