leetcode264

先给出一个我自己写的方案，TLE

 1 class Solution:
 2     def __init__(self):
 3         self.memo = dict()
 4         self.memo[1] = True
 5 
 6     def isUgly(self,num):
 7         if num <= 0:
 8             return False
 9         if num == 1:
10             return True
11         if num % 2 == 0:
12             p = num // 2
13             if p in self.memo:
14                 return self.memo[p]
15             else:
16                 return self.isUgly(p)
17         if num % 3 == 0:
18             p = num // 3
19             if p in self.memo:
20                 return self.memo[p]
21             else:
22                 return self.isUgly(p)
23         if num % 5 == 0:
24             p = num // 5
25             if p in self.memo:
26                 return self.memo[p]
27             else:
28                 return self.isUgly(p)
29         return False
30 
31     def nthUglyNumber(self, n: int) -> int:
32         i,j = 1,2
33         while i != n:
34             self.memo[j] = self.isUgly(j)
35             if self.memo[j] == True:
36                 i += 1
37             j += 1
38         return j - 1

再给出一个AC的方案，使用动态规划：

 1 class Solution:
 2     def nthUglyNumber(self, n: int) -> int:
 3         dp = [1]*n
 4         p2, p3, p5 = 0, 0, 0
 5         for i in range(1, n):
 6             cur = min(2*dp[p2], 3*dp[p3], 5*dp[p5])
 7             if cur == 2*dp[p2]:
 8                 p2 += 1
 9             if cur == 3*dp[p3]:
10                 p3 += 1
11             if cur == 5*dp[p5]:
12                 p5 += 1
13             dp[i] = cur
14         return dp[-1]