Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
第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]

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理