题目描述
给你一根长度为 n 绳子,请把绳子剪成 m 段(m、n 都是整数,2≤n≤58 并且 m≥2)。
每段的绳子的长度记为 k[1]、k[2]、……、k[m]。
k[1]k[2]…k[m] 可能的最大乘积是多少?
例如当绳子的长度是 8 时,我们把它剪成长度分别为 2、3、3 的三段,此时得到最大的乘积 18。
样例
输入:8
输出:18
-
首先判断k[1]到k[m]可能有哪些数字,实际上只可能是2或者3。
-
当然也可能有4,但是4=2*2,我们就简单些不考虑了。
-
5 < 2 * 3, 6 < 3 * 3,比6更大的数字我们就更不用考虑了,肯定要继续分。
-
其次看2和3的数量,2的数量肯定小于3个,为什么呢?因为2 * 2 * 2 < 3 * 3,那么题目就简单了。
-
直接用n除以3,根据得到的余数判断是一个2还是两个2还是没有2就行了。
-
由于题目规定m>1,所以2只能是1 * 1,3只能是2 * 1,这两个特殊情况直接返回就行了。
-
乘方运算的复杂度为:O(log n)。
Java 代码
class Solution{
public int maxProductAfterCutting(int length)
{
if(length == 2){
return 1;
}
int x = length % 3;
int y = length / 3;
if(x == 0){
return (int)Math.pow(3, y);
}else if(x == 1){
return (int)Math.pow(3, y-1)*2*2;
}else{
return (int)Math.pow(3, y)*2;
}
}
}