Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

寫一下昨天的

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]
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.221.50 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724071407.A.911.html
推 DJYOMIYAHINA: 我有什麼用
→ sustainer123: 我有什麼用