leetcode 343. Integer Break

233jl 發(fā)布于2019-08-15 14:44 / 1978人閱讀

摘要：題目要求將一個(gè)正整數(shù)分解為兩個(gè)或兩個(gè)以上的正整數(shù)，要求這些正整數(shù)的乘積最大。思路和代碼這里應(yīng)用了一個(gè)數(shù)學(xué)的思路。假設(shè)我們有一個(gè)數(shù)字，該數(shù)組可以隨機(jī)分解為和。因此取時(shí)可以得到最好的結(jié)果。至于為什么我們需要盡可能用分解，因?yàn)椤?/p>

題目要求

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. 
Return the maximum product you can get.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: You may assume that n is not less than 2 and not larger than 58.

將一個(gè)正整數(shù)分解為兩個(gè)或兩個(gè)以上的正整數(shù)，要求這些正整數(shù)的乘積最大。

思路和代碼

這里應(yīng)用了一個(gè)數(shù)學(xué)的思路。假設(shè)我們有一個(gè)數(shù)字n，該數(shù)組可以隨機(jī)分解為t和n-t。當(dāng)分解為n/2時(shí)可以獲得最大的乘積。因此t取n/2時(shí)可以得到最好的結(jié)果。但是這里我們明顯還可以繼續(xù)對(duì)t分解（如果t大于1），這樣逐個(gè)分解之后終歸會(huì)分解為2或者1為質(zhì)因數(shù)

假設(shè)N為偶數(shù)，(N/2)*(N/2)>=N, 則 N>=4
假設(shè)N為奇數(shù)，(N-1)/2 *(N+1)/2, 則 N>=5

因此分解的數(shù)小于4。

至于為什么我們需要盡可能用3分解，因?yàn)?b>3*3>2*2*2。

    public int integerBreak(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        
        int product = 1;
        while(n >4){
            product *= 3;
            n -= 3;
        }
        
        product *= n;
        return product;
    }

想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~