题目描述

给你一根长度为 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);
    }
};