[Leetcode] Ugly Number 丑陋数

RobinQu 发布于2019-08-14 16:09 / 3271人阅读

摘要：如果有一个方法能够顺序只生成丑陋数就好了。仔细观察可以发现，丑陋数的因子也必定是丑陋数，它一定是某个丑陋数乘得到的。不过，我们可以确定的是，小的丑陋数乘，肯定小于大的丑陋数乘。

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

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

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