写一下昨天的
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]
}