题目描述
给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]k[1]...*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18
参考LeetCode上的题解
尽可能将绳子以长度 3 等分为多段时,乘积最大。
切分规则:
把绳子尽可能切为多个长度为 3的片段;
若最后一段绳子长度为 2;则保留,不再拆为 1 + 1 。
若最后一段绳子长度为 1;则应把一份 3 + 1替换为 2 + 2。
class Solution { public: int cuttingRope(int n) { int ans; if(n==2) return 1;//长度为2和为3的要单独判断(易错点!!!) if(n==3) return 2; if(n%3==0) ans=pow(3,n/3); else if(n%3==1) ans=pow(3,n/3-1)*4; else ans=pow(3,n/3)*2; return ans; } };
剪绳子Ⅱ
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
分来一段段求余数,所以每次ans乘一次3就求一次余数,同时n也减去3.
这里ans还是要用longlong
n>4的循环条件可以规避前面剩1 2 0的情况
class Solution { public: int cuttingRope(int n) { if (n == 2) return 1; if (n == 3) return 2; if (n == 4) return 4; long long int ans=1;//不然会报错 while(n>4){ ans*=3; ans%=1000000007; n-=3; } //跳出循环时只可能是4 3 2 不可能是1,因为提前就4跳出了 return (ans*n%1000000007); } };