給你一根長(zhǎng)度為 n 的繩子，請(qǐng)把繩子剪成整數(shù)長(zhǎng)度的 m 段（m、n都是整數(shù)，n>1并且m>1），每段繩子的長(zhǎng)度記為 k[0],k[1]...k[m] 。請(qǐng)問 k[0]*k[1]*...*k[m] 可能的最大乘積是多少？例如，當(dāng)繩子的長(zhǎng)度是8時(shí)，我們把它剪成長(zhǎng)度分別為2、3、3的三段，此時(shí)得到的最大乘積是18。

示例 1：

輸入: 2
輸出: 1
解釋: 2 = 1 + 1, 1 × 1 = 1
示例?2:

輸入: 10
輸出: 36
解釋: 10 = 3 + 3 + 4, 3 ×?3 ×?4 = 36
提示：

2 <= n <= 58

思路：

盡量分成長(zhǎng)度為3的，乘積會(huì)大，剩下的都是長(zhǎng)度為2的

4是個(gè)特例，所以分成長(zhǎng)度為3的時(shí)候，如果剩下的長(zhǎng)度為1，長(zhǎng)度為3的就少分一段

代碼：

class?Solution?{

????public?int?cuttingRope(int?n)?{

????????if(n==2)

????????{

????????????return?1;

????????}

????????if(n==3)

????????{

????????????return?2;

????????}

????????int?count1=0,count2=0;

????????count1?=?n/3;

????????if(n-count1*3==1&&count1>0)

????????{

????????????count1-=1;

????????}

????????count2?=?n-count1*3;

????????count2?/=2;

????????int?result?=?1;

????????for(int?i=1;i<=count1;i++)

????????{

????????????result*=3;

????????}

????????for(int?i=1;i<=count2;i++)

????????{

????????????result*=2;

????????}

????????return?result;

????}

}

總結(jié)

以上是生活随笔為你收集整理的【剑指offer】面试题14- I：剪绳子（Java）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。