Write a PRogram to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note that 1 is typically treated as an ugly number, and n does not exceed 1690.
找到第n個丑數(shù)。丑數(shù)是有限個2、3、5的乘積，例如1，2，3，4，5，6，8，9，10，12是前10個丑數(shù)（1是特殊的丑數(shù)）。n不大于1690
動態(tài)規(guī)劃解。我剛開始考慮的是dp[i]代表i是否為丑數(shù)，它的確定只需要知道dp[i % 2], dp[i % 3]和dp[i % 5]，只要有一個是丑數(shù)，那么dp[i]必然也是丑數(shù)，然后統(tǒng)計丑數(shù)的個數(shù)直到n?？墒沁@樣我沒法確定到底dp需要多大，所以需要換個思路。dp[i]應(yīng)該代表第i個丑數(shù)，那么它的遞推關(guān)系該怎么找呢？其實很簡單，因為下一個丑數(shù)必然是乘以2，3或5中的最小的那個數(shù)，所以我們只需分別記下乘以2，乘以3，乘以5的最小的數(shù)的索引，那么 dp[i] = min(dp[index_2] * 2, dp[index_3] * 3, dp[index_5] * 5)，每次得到dp[i]不要忘了更新索引就可以了（注意：因為有可能dp[index_2] * 2和dp[index_3] * 3是相等的，這種情況，兩個索引都要更新)
class Solution(object): def nthUglyNumber(self, n): """ :type n: int :rtype: int """ dp = [0] * n # 1為第一個丑數(shù) dp[0] = 1 # 從1開始向前尋找 index_2, index_3, index_5 = 0, 0, 0 for i in range(1, n): dp[i] = min(dp[index_2] * 2, dp[index_3] * 3, dp[index_5] * 5) # 這里不要elif，因為兩個值可能相等，索引都需要更新 if dp[i] == dp[index_2] * 2: index_2 += 1 if dp[i] == dp[index_3] * 3: index_3 += 1 if dp[i] == dp[index_5] * 5: index_5 += 1 return dp[n - 1]新聞熱點
疑難解答
