复杂度基本是O(1)级别。
对于相乘最大问题,数学上可以这么理解:如果两个数,那么理解为周长相等的矩形,正方形面积比长方形的大;如果三个数,那么理解为立方体的体积比长方体的大……以此类推。
也就是说,m个数相加等于n,找到一个数curr,curr的m次方大于等于n,那么curr就是我们要找的绳子的段数,当然最后会有一段绳子小于等于curr。具体算法如下
public class Solution {
public int cutRope(int target) {
if(target == 2) return 1;
int curr = 1;
while(true){
if(curr * curr >= target) break;
curr++;
}
int res = 1;
while(target > curr){
res *= curr;
target -= curr;
}
res *= target;
return res;
}
}


京公网安备 11010502036488号