[LeetCode] Coin Change

https://leetcode.com/problems/coin-change

最近開始刷leetcode覺得思考這些邏輯問題還滿好玩的
第一個刷的是這個,他是一個動態規劃的題目

一般我們在思考的時候會去思考以錢幣為基準,例如1,3,5的錢幣要怎麼湊成11元,我們會拿1,3,5去隨機湊硬幣,但是當數值大了以後,要計算最小的錢幣組合就會變成很困難.

像這種極限求值就會需要將思考轉換過來, 我們可以一步步的拆解, 先了解1,3,5,若要組成1是用幾個(1個1),那組成2要用幾個(2個1),若要組成3要用幾個,到3時我們就會發現,3可以用”3個1″或”1個3″組成, 這時候就可以來比較誰用的硬幣比較少,然後把最小可組成的數字”1″存到可組成結果為3的陣列。
接下來在思考4的時候,我們就可以思考4減掉硬幣1,也就是3,的最小使用硬幣數量,那就代表我們使用3,再加上硬幣1,可以組成4。接下來算要組成6要幾個硬幣,6減掉硬幣3,可以拿到硬幣3要用幾個硬幣,所以就是硬幣3使用的硬幣數量+1。

這個JS的效能只贏了32.59%的人

覺得不太開心(?)
所以我把console.log拿掉,再把let amountRecord = []; amountRecord[0] = 0;改成一行let amountRecord = [0](是有沒有這麼無聊)

接著我突發奇想,想說若是這個數字可用硬幣湊齊, 下個數字如果小於最小的coins數字的話,可以省略(如硬幣是10,15,18, 但是要組成11,很明顯就不可能會有結果,因為11-10小於10)

PS: 但是測試後其實拿掉console.log影響最大XD

結果如下

好啦至少擊敗了72.28%的人,累了…先這樣吧XDD

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *