作者:
JIWP (JIWP)
2024-08-19 20:43:23寫一下昨天的
264. Ugly Number II
ugly number是一個由2^i*3^j*5^k的正整數
請回傳第n小ugly number
思路:
一看到題目就知道應該是DP
不過我dp很爛，寫超久
首先建立一個長度n的dp矩陣，來放ugly number
我們會知道1就是第一個ugly number
ugly number都是由比較小的ugly number乘上2、3、5得到的
所以我們建立三個index分別代表2、3、5接下來要乘以dp矩陣中哪個元素
dp矩陣的最新一個元素是由min(2*dp[idx1],3*dp[idx2],5*dp[idx3])得到
當2*dp[idx1] or 3*dp[idx2] or 5*dp[idx3]與最新一個元素相等
對應的idx就要往前移1
最後回傳dp[n-1]就好
golang code :
func nthUglyNumber(n int) int {
dp := make([]int, n)
dp[0] = 1
i := 1
idx2, idx3, idx5 := 0, 0, 0
factor2, factor3, factor5 := 2, 3, 5
for i < n {
minnum := min(min(factor2, factor3), factor5)
dp[i] = minnum
if minnum == factor2 {
idx2++
factor2 = dp[idx2] * 2
}
if minnum == factor3 {
idx3++
factor3 = dp[idx3] * 3
}
if minnum == factor5 {
idx5++
factor5 = dp[idx5] * 5
}
i++
}
return dp[n-1]
}