1、题目
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1：
输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
2、解答
- 动态规划：对于第n个丑数，就是前面n-1个丑数与[2、3、5]相乘对应的最小值。但是这里有可以优化的点就是我们不需要把前面n-1个丑数都遍历一遍，而是可以考虑记录已经遍历过的数。然后考虑丑数其实就是这些质因数相乘所得，那么可以考虑记录每一个质因数使用的计数。
class Solution(object):
def nthUglyNumber(self, n):
"""
动态规划法：其实dp[n] = min(dp[0~n-1]*[2,3,5])
维护一个visited类似的记录在因子2，3，5都已经使用的次数
:type n: int
:rtype: int
"""
if n == 1:
return 1
dp = [0] * n
dp[0] = 1
# 因子使用的次数
p2 = p3 = p5 = 0
for i in range(1, n):
dp[i] = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)
if dp[i] == dp[p2] * 2:
p2 += 1
if dp[i] == dp[p3] * 3:
p3 += 1
if dp[i] == dp[p5] * 5:
p5 += 1
return dp[-1]
|