剑指offer-剪绳子ⅠⅡ（中等）

题目描述

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