成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode 343. Integer Break

233jl / 1980人閱讀

摘要：題目要求將一個(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ù)對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;
    }


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

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/68790.html

相關(guān)文章

  • LeetCode 343. Integer Break

    摘要：思路動(dòng)態(tài)規(guī)劃，前五個(gè)數(shù)的最大乘積為，后面的第個(gè)數(shù)的最大乘積，由從后往前數(shù)包括本身的第三個(gè)數(shù)乘以得到。何睿何睿前個(gè)數(shù)的最大乘積動(dòng)態(tài)規(guī)劃第個(gè)數(shù)的最大乘積為往前數(shù)第三個(gè)數(shù)思路與上面的思路一致，優(yōu)化了空間源代碼文件在這里。 Description Given a positive integer n, break it into the sum of at least two positive...

    ckllj 評論0 收藏0

  • [LeetCode] Integer Break

    Problem 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...

    leonardofed 評論0 收藏0

  • [LeetCode] 811. Subdomain Visit Count

    Problem A website domain like discuss.leetcode.com consists of various subdomains. At the top level, we have com, at the next level, we have leetcode.com, and at the lowest level, discuss.leetcode.com...

    jzman 評論0 收藏0

  • [Leetcode] Evaluate Reverse Polish Notation 計(jì)算逆波蘭表

    摘要：棧法復(fù)雜度時(shí)間空間思路逆波蘭表達(dá)式的計(jì)算十分方便，對于運(yùn)算符，其運(yùn)算的兩個(gè)數(shù)就是這個(gè)運(yùn)算符前面的兩個(gè)數(shù)。注意對于減法，先彈出的是減號(hào)后面的數(shù)。 Evaluate Reverse Polish Notation Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operato...

    ephererid 評論0 收藏0

  • [LeetCode] 8. String to Integer (atoi)

    Problem Implement function atoi to convert a string to an integer. If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values...

    cuieney 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<