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個(gè)丑數(shù)。丑數(shù)是有限個(gè)2、3、5的乘積，例如1，2，3，4，5，6，8，9，10，12是前10個(gè)丑數(shù)（1是特殊的丑數(shù)）。n不大于1690
動(dòng)態(tài)規(guī)劃解。我剛開始考慮的是dp[i]代表i是否為丑數(shù)，它的確定只需要知道dp[i % 2], dp[i % 3]和dp[i % 5]，只要有一個(gè)是丑數(shù)，那么dp[i]必然也是丑數(shù)，然后統(tǒng)計(jì)丑數(shù)的個(gè)數(shù)直到n。可是這樣我沒法確定到底dp需要多大，所以需要換個(gè)思路。dp[i]應(yīng)該代表第i個(gè)丑數(shù)，那么它的遞推關(guān)系該怎么找呢？其實(shí)很簡(jiǎn)單，因?yàn)橄乱粋€(gè)丑數(shù)必然是乘以2，3或5中的最小的那個(gè)數(shù)，所以我們只需分別記下乘以2，乘以3，乘以5的最小的數(shù)的索引，那么 dp[i] = min(dp[index_2] * 2, dp[index_3] * 3, dp[index_5] * 5)，每次得到dp[i]不要忘了更新索引就可以了（注意：因?yàn)橛锌赡躣p[index_2] * 2和dp[index_3] * 3是相等的，這種情況，兩個(gè)索引都要更新)
class Solution(object): def nthUglyNumber(self, n): """ :type n: int :rtype: int """ dp = [0] * n # 1為第一個(gè)丑數(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，因?yàn)閮蓚€(gè)值可能相等，索引都需要更新 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]新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
