Posted on 2022-11-18 20:09
Uriel 閱讀(40)
評論(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]