leetcode Ugly Number I II

leetcode 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.

题目地址: leetcode Ugly Number

题意：

Ugly numbers 是一个只能被2，3，5整除的数，给你一个数，判断是否是 ugly number

思路：

直接分别除2，3，5。。。看看最后是不是1

注意0的情况

C++

class Solution {
public:
    bool isUgly(int num) {
        if(num == 0) return false;
        for (int x : vector<int>{2,3,5})
            while (num % x == 0) num /= x;
        return num == 1;
    }
};

Java

class Solution {
    public boolean isUgly(int num) {
        if(num == 0) return false;
        for (int x : new int[]{2, 3, 5})
            while (num % x == 0) num /= x;
        return num == 1;
    }
}

Python

class Solution(object):
    def isUgly(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if not num: return False
        for x in (2, 3, 5):
            while num % x == 0:
                num /= x
        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.

题目地址: leetcode Ugly Number II

题意：

Ugly numbers 是一个只能被2，3，5整除的数，求第n个Ugly number

思路：

方法1

优先队列，每次取出当前的ugly number，然后乘上2,3,5

*2：肯定是没放入队列中的
*3：若一个数不是6的倍数，那么说明肯定没有加入队列中，可以加入
*5：若不是10或者15的倍数，说明也没加入到队列中

复杂度：nlogn

class Solution {
public:
    int nthUglyNumber(int n) {
        priority_queue<long long> q;
        q.push(-1);
        while (--n > 0) {
            long long x = -q.top();
            q.pop();
            long long a = x * 2;
            long long b = x * 3;
            long long c = x * 5;
            q.push(-a);
            if (b % 6 != 0) {
                q.push(-b);
            }
            if (c % 10 != 0 && c % 15 != 0) {
                q.push(-c);
            }
        }
        return -q.top();
    }
};

方法2：

我们来看看，要如何求第n个ugly number.

第一个ugly number 是1 我们讨论n大于1的情况

因为它只能被2，3，5整除，所以我们从1开始扩展，每次要么乘2，要么乘3，要么乘5.

对于1来说，我们分别乘以2，3，5得到[2,3,5]，显然2是最小的。

于是第2个ugly number是2。

接着第3个呢？显然是 3 . 从 1 * 3 得到

第4个就不一样了，它是从2*2得到。

这有什么规律呢？规律就是，每个因子分别乘以当前得到的ugly number（初始为1），当某因子x算出来的不大于其他两个因子，说明新的ugly number是当前因子算出来的，下一轮，该因子应该乘以之前ugly number的下一个。

换句话说，每个因子分别乘以对应的ugly number[i]后，如果得到了新的ugly number 就说明下一次应该乘以下一个（ugly number[i+1]）。这样能保证乘出来的小而且不会漏掉。

另一种理解：一个丑数*2， *3， *5 就会得到另外的一个丑数，那么已知n个丑数，要得到n + 1个丑数的时候，必然是从前n个丑数*2， *3， *5 得到的。因此就变成了一个合并三个有序数组的问题：维护三个指针a, b, c，比较各自*2， *3， *5 得到的值最小（设为cur），则放入第 n + 1个位置。同时，为了不产生重复解，下面的代码用了if而不是else if来跳过重复解。

详见代码：

C++

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n, 1);
        int a = 0, b = 0, c = 0;
        for (int i = 1; i < n; ++i) {
            int cur = min({dp[a] * 2, dp[b] * 3, dp[c] * 5});
            if (cur == dp[a] * 2) ++a;
            if (cur == dp[b] * 3) ++b;
            if (cur == dp[c] * 5) ++c;
            dp[i] = cur;
        }
        return dp.back();
    }
};

Java

class Solution {
    public int nthUglyNumber(int n) {
        int[] ans = new int[n];
        ans[0] = 1;
        int a = 0, b = 0, c = 0;
        for (int i = 1; i < n; i++) {
            int cur = Math.min(ans[a] * 2, Math.min(ans[b] * 3, ans[c] * 5));
            ans[i] = cur;
            if (ans[a] * 2 == cur) a++;
            if (ans[b] * 3 == cur) b++;
            if (ans[c] * 5 == cur) c++;
        }
        return ans[n - 1];
    }
}

Python

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        a = b = c = 0
        ans = [1] * n
        for i in range(1, n):
            ans[i] = min(ans[a] * 2, ans[b] * 3, ans[c] * 5)
            if ans[a] * 2 == ans[i]: a += 1
            if ans[b] * 3 == ans[i]: b += 1
            if ans[c] * 5 == ans[i]: c += 1
        return ans[n - 1]

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/