Re: [閒聊] 每日LeetCode

看板Marginalman作者AyuniD (アユニ．Ｄ)時間6月前 (2023/10/06 20:12)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串439/719 (看更多)

確實是數學題，但我是用 DP 去解的對於所有大於 6 的數字，要嘛拔 2 要嘛拔 3 意即： res(n) = max(2 * res(n-2), 3 * res(n-3)) for all n > 6 為什麼是 6 呢？先從前面幾個數字看起： 2 -> 1 + 1, res(2) = 1 3 -> 1 + 2, res(3) = 2 4 -> 2 + 2, res(4) = 4 — 這邊如果直接代我上面的公式，會使得 4 被拆成 2+1+1 5 -> 2 + 3, res(5) = 6 — 同上，會拆出 1 來 6 -> 3 + 3, res(6) = 9 — 同上關於這其中的道理我還不太懂，但猜想有可能是因為 6 以下的數字，2 和 3 出現的次數會是 1 次或 0 次，沒辦法用公式解那為什麼拔 2 或 3 就可以？往上看幾個：拔 4 -> 等同於拔兩個 2 拔 5 -> res(5) = 6，一定小於分開拔 2 跟 3 拔 6 -> 同上，拔出來的數字會使得成績變小 … 以此類推沒辦法給出詳細的證明，但我想 idea 差不多就這樣 Code: class Solution: def __init__(self): self.table = [-1, -1, 1, 2, 4, 6, 9] def integerBreak(self, n: int) -> int: while n > len(self.table) - 1: length = len(self.table) self.table.append(max(2 * self.table[length - 2], 3 * self.table[len gth - 3])) return self.table[n] Ps: 其實這題單純用遞迴解也可以，只是 Python 寫這類題目通常都會 TLE，所以我才直接用 D P Table 可能因為這題的 n 只到 58 吧，if-else 硬幹也能過 Code: class Solution: def integerBreak(self, n: int) -> int: if n == 2: return 1 elif n == 3: return 2 elif n == 4: return 4 elif n == 5: return 6 elif n == 6: return 9 else: return max(2 * self.integerBreak(n-2), 3 * self.integerBreak(n-3)) Ps2: 或你想要 fancy 一點用 match-case 也可以，意思一樣： Code: class Solution: def integerBreak(self, n: int) -> int: match n: case 2: return 1 case 3: return 2 case 4: return 4 case 5: return 6 case 6: return 9 case _: return max(2 * self.integerBreak(n-2), 3 * self.integerBreak (n-3)) ※ 引述《ZooseWu》之銘言： : 標題：Re: [閒聊] 每日LeetCode : 時間: Fri Oct 6 15:52:22 2023 : : ※ 引述《yam276 (史萊哲林的優等生)》之銘言： : : 343. Integer Break : : 把整數拆成相加的數字 : : 取這些數字最大乘積 : 這題我是以遞迴的思路去想的 : : 對於任意數x 他拆分後的最大乘積res(x) : : res(x)=res(x1)*res(x2) (x1+x2=x) : : 不會證明 : : 乘法有結合律 : : 想一下應該能得出這個結論 : : : : 所以每個數都可以拆成更小的兩個數找最大乘積 : : 我們只要找到遞迴的終點就能知道怎麼反推回來 : : 2=>2 : 3=>3 : 4=>4 : 5=>3*2 : 6=>3*3 : : 能夠知道最小拆分就是3 能拆越多3就越大 : : 然後4是例外 2*2>3*1 : : 除此之外還題目還限制每個數字至少要拆成兩個數 : : 所以2跟3會有特殊解1跟2 : : : code: : : function integerBreak (n: number): number { : if (n === 2) return 1 //特殊解 : else if (n === 3) return 2 //特殊解 : : let result = Math.pow(3, Math.floor(n / 3)) //計算有幾個3 : if (n % 3 === 1) result *= 4 / 3 //最後是4 要少拆一次3 : else if (n % 3 === 2) result *= 2 : return result : } : : -- : Zoosewu : Yoututbe顯示PTT推文 : 可以在各個網站追實況或Live時使用 : 預覽圖: https://i.imgur.com/ZhtXdAJ.png

https://i.imgur.com/WqbLNV3.png

: 完整介紹: https://github.com/zoosewu/PTTChatOnYoutube/tree/master/homepage : 支援的網站: Youtube Twitch Holotools Niji-mado Holodex : : -- : ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣) : ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1696578745.A.75D.html : ※ 編輯: ZooseWu (114.32.229.33 臺灣), 10/06/2023 15:53:14 -- 僕の妹がこんなに可愛いわけがない担当のアユニ‧D です https://i.imgur.com/Zvo15mG.jpg