LeetCode 上的丑数问题

动态规划

题目背景

把只包含因子 $2$、$3$ 和 $5$ 的数称作丑数（Ugly Number）。例如 $6$、$8$ 都是丑数，但 $14$ 不是，因为它包含因子 $7$。 习惯上我们把 $1$ 当做是第一个丑数。求按从小到大的顺序的第 $N$ 个丑数。

关于丑数，LeetCode 有如下 3 个问题，难度都在中等以下。

LeetCode 第 263 题：263. 丑数

这道题要求我们判断一个数是不是丑数。

编写一个程序判断给定的数是否为丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例 1:

输入: 6
输出: true
解释: 6 = 2 × 3

示例 2:

输入: 8
输出: true
解释: 8 = 2 × 2 × 2

示例 3:

输入: 14
输出: false 
解释: 14 不是丑数，因为它包含了另外一个质因数 7。

说明：

1. 1 是丑数。
2. 输入不会超过 32 位有符号整数的范围: [−231, 231 − 1]。

要求：编写一个程序判断给定的数是否为丑数。丑数就是只包含质因数 $2$, $3$, $5$ 的正整数。

class Solution:
    def isUgly(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num <= 0:
            return False
        while num % 2 == 0:
            num //= 2
        while num % 3 == 0:
            num //= 3
        while num % 5 == 0:
            num //= 5
        return num == 1

等价的写法：

class Solution:
    def isUgly(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num <= 0:
            return False
        factors = [2, 3, 5]
        for factor in factors:
            while num % factor == 0:
                num //= factor
        return num == 1

LeetCode 第 264 题：264. 丑数 II

丑数的生成。

编写一个程序，找出第 n 个丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

1. 1 是丑数。
2. n **不超过**1690。

这一系列问题关键在于丑数是如何生成的。

根据以上分析，注意一下以下代码的写法，思路是这样的：

1、先把这个数找到；

2、然后找这个数是哪个索引过来的，如果是这个索引，这个索引就加 $1$，例如：

while nums[M2] * 2 <= nums[index]:
    M2 += 1

此时 M2 来到了第 1 个使得 nums[M2] * 2 <= nums[index] 的地方，这里 nums[index] 表示当前得到的最小的“丑数”。

Python 代码：

class Solution:
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 0:
            return 0
        if n == 1:
            return 1
        # 索引从 0 开始
        M2 = 0
        M3 = 0
        M5 = 0
        nums = [None for _ in range(n)]
        nums[0] = 1
        for index in range(1, n):
            nums[index] = min(nums[M2] * 2, nums[M3] * 3, nums[M5] * 5)
            while nums[M2] * 2 <= nums[index]:
                M2 += 1
            while nums[M3] * 3 <= nums[index]:
                M3 += 1
            while nums[M5] * 5 <= nums[index]:
                M5 += 1
        return nums[n - 1]

根据以上的分析，不难写出 LeetCode 第 313 题。

LeetCode 第 313 题：超级丑数

编写一段程序来查找第 *n* 个超级丑数。

超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。

示例:

输入: n = 12, primes = [2,7,13,19]
输出: 32 
解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。

说明:

• 1 是任何给定 primes 的超级丑数。
• 给定 primes 中的数字以升序排列。
• 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。
• 第 n 个超级丑数确保在 32 位有符整数范围内。

Python 代码：

class Solution:
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        if n <= 0:
            return 0
        if n == 1:
            return 1
        l = len(primes)
        indexes = [0 for _ in range(l)]
        nums = [None for _ in range(n)]
        nums[0] = 1
        for i in range(1, n):
            res = float('inf')
            for j in range(l):
                res = min(res, primes[j] * nums[indexes[j]])
            nums[i] = res
            for j in range(l):
                if nums[indexes[j]] * primes[j] <= res:
                    indexes[j] += 1
        return nums[n - 1]

（本节完）