Re: [閒聊] 每日LeetCode

[ZooseWu (動物園 公告)]

※ 引述《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