Re: [閒聊] 每日LeetCode

[yam276 (史萊哲林的優等生)]

343. Integer Break

把整數拆成相加的數字

取這些數字最大乘積


思路：

這題是數學題 不是程式題==

數字4拆成 2+2    積最大為 4
數字5拆成 3+2    積最大為 6
數字6拆成 3+3    積最大為 9
數字7拆為 3+4    積最大為 12
數字8拆為 3+3+2  積最大為 18
數字9拆為 3+3+3  積最大為 27
數字10拆為 3+3+4 積最大為 36

找規律可以得知拆成一堆3最大

並且3*3*4也比3*3*3*1大

因此n % 3 = 1要特別處理


Code:

impl Solution {
    pub fn integer_break(n: i32) -> i32 {
        match n {
            2 => return 1,
            3 => return 2,
            _ => {}
        }

        let result = match n % 3 {
            1 => 3i32.pow((n / 3 - 1) as u32) * 4,
            2 => 3i32.pow((n / 3) as u32) * 2,
            _ => 3i32.pow((n / 3) as u32),
        };
        result
    }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.172 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1696562979.A.C55.html
※ 編輯: yam276 (60.248.143.172 臺灣), 10/06/2023 11:30:04
→ PyTorch: 大師
推 Rushia: 大師
→ NTHUlagka: 大師
推 wwndbk: 大師