[关闭]
@liweiwei1419 2019-05-24T00:42:49.000000Z 字数 2142 阅读 1474

LeetCode 上的丑数问题

动态规划



题目背景

把只包含因子 的数称作丑数(Ugly Number)。例如 都是丑数,但 不是,因为它包含因子 。 习惯上我们把 当做是第一个丑数。求按从小到大的顺序的第 个丑数。

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

LeetCode 第 263 题:263. 丑数

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

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

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

示例 1:

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

示例 2:

  1. 输入: 8
  2. 输出: true
  3. 解释: 8 = 2 × 2 × 2

示例 3:

  1. 输入: 14
  2. 输出: false
  3. 解释: 14 不是丑数,因为它包含了另外一个质因数 7

说明:

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

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

  1. class Solution:
  2. def isUgly(self, num):
  3. """
  4. :type num: int
  5. :rtype: bool
  6. """
  7. if num <= 0:
  8. return False
  9. while num % 2 == 0:
  10. num //= 2
  11. while num % 3 == 0:
  12. num //= 3
  13. while num % 5 == 0:
  14. num //= 5
  15. return num == 1

等价的写法:

  1. class Solution:
  2. def isUgly(self, num):
  3. """
  4. :type num: int
  5. :rtype: bool
  6. """
  7. if num <= 0:
  8. return False
  9. factors = [2, 3, 5]
  10. for factor in factors:
  11. while num % factor == 0:
  12. num //= factor
  13. return num == 1

LeetCode 第 264 题:264. 丑数 II

丑数的生成。

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

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

示例:

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

说明:

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

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

image-20190119153815599

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

1、先把这个数找到;

2、然后找这个数是哪个索引过来的,如果是这个索引,这个索引就加 ,例如:

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

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

Python 代码:

  1. class Solution:
  2. def nthUglyNumber(self, n):
  3. """
  4. :type n: int
  5. :rtype: int
  6. """
  7. if n <= 0:
  8. return 0
  9. if n == 1:
  10. return 1
  11. # 索引从 0 开始
  12. M2 = 0
  13. M3 = 0
  14. M5 = 0
  15. nums = [None for _ in range(n)]
  16. nums[0] = 1
  17. for index in range(1, n):
  18. nums[index] = min(nums[M2] * 2, nums[M3] * 3, nums[M5] * 5)
  19. while nums[M2] * 2 <= nums[index]:
  20. M2 += 1
  21. while nums[M3] * 3 <= nums[index]:
  22. M3 += 1
  23. while nums[M5] * 5 <= nums[index]:
  24. M5 += 1
  25. return nums[n - 1]

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

LeetCode 第 313 题:超级丑数

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

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

示例:

  1. 输入: n = 12, primes = [2,7,13,19]
  2. 输出: 32
  3. 解释: 给定长度为 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 代码:

  1. class Solution:
  2. def nthSuperUglyNumber(self, n, primes):
  3. """
  4. :type n: int
  5. :type primes: List[int]
  6. :rtype: int
  7. """
  8. if n <= 0:
  9. return 0
  10. if n == 1:
  11. return 1
  12. l = len(primes)
  13. indexes = [0 for _ in range(l)]
  14. nums = [None for _ in range(n)]
  15. nums[0] = 1
  16. for i in range(1, n):
  17. res = float('inf')
  18. for j in range(l):
  19. res = min(res, primes[j] * nums[indexes[j]])
  20. nums[i] = res
  21. for j in range(l):
  22. if nums[indexes[j]] * primes[j] <= res:
  23. indexes[j] += 1
  24. return nums[n - 1]

(本节完)

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注