Posted on 2022-11-18 20:09
Uriel 阅读(26)
评论(0) 编辑 收藏 引用 所属分类:
DP 、
闲来无事重切Leet Code
第263题的姐妹题，第263题
判断一个数的因数是否只有2，3，5，第264题输出第n个因数只有2，3，5的数（n<= 1690）
dp思想，dp[i]存第i个符合要求的数，p2，p3，p5记录当前已经用了多少次2，3和5，dp[i] = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)
1 #264
2 #Runtime: 123 ms
3 #Memory Usage: 13.5 MB
4
5 class Solution(object):
6 def nthUglyNumber(self, n):
7 """
8 :type n: int
9 :rtype: int
10 """
11 p2, p3, p5 = 1, 1, 1
12 dp = [0] * (n + 1)
13 dp[1] = 1
14 for i in range(2, n + 1):
15 dp[i] = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)
16 if dp[i] == dp[p2] * 2:
17 p2 += 1
18 if dp[i] == dp[p3] * 3:
19 p3 += 1
20 if dp[i] == dp[p5] * 5:
21 p5 += 1
22 return dp[n]