剑指 Offer 14- II. 剪绳子 II

n在[2,1000]之间，存在大数问题

贪心算法

思路

将n分解为a个3，其余数为p；

• p==0时，则;
• p==1时，则; 显然4>1*3;
• p==2时，则; 显然5<2*3;

实现

    //循环求余法
    int mod=1e9+7;
    int cuttingRope(int n){
        int ret=1;
        while(n>4){
            ret=(ret*3)%mod;
            n-=3;
        }
        return ret*n%mod;
    }

复杂度分析

• 时间复杂度:
• 空间复杂度:

❤❤❤快速幂求余

思路

实现

    int mod=1e9+7;
    int cuttingRope(int n){
        long ret=1;
        int a=n/3,p=n%3;
        long x=3;
        if(p==2) {
            a-=1;
            p=4;
        }
        while(a>0){
            if(a&1) ret=(ret*x)%mod;
            x=(x*x)%mod;
            a>>=1;
        }
        if(p) ret=(ret*p)%mod;
        return ret;
    }

复杂度分析

• 时间复杂度:
• 空间复杂度:

题目标题难度划分

算法掌握难度程度划分