【数学知识】剑指 Offer 14- II. 剪绳子 II-跟着帅地玩副业，开拓第二曲线PlayOffer

hi 普通 2023年8月19日上午8:48

res 结果那里得先取余再赋值res=(res3)%p，不能写成res=3%p

class Solution {
public:
    int cuttingRope(int n) {
        if(n <= 3) return n-1;
        long long res = 1;
        int p = 1000000007;
        if(n % 3 == 1) res = 4, n -= 4;
        else if(n % 3 == 2) res = 2, n -= 2;
        while(n){
            res = (res * 3) % p;
            n -= 3;
        } 
        return res;
    }
};

0 赞同 0 条回复

艺普通 2023年8月4日下午4:18

“`c++
class Solution {
public:
int cuttingRope(int n) {
if (n == 2) return 1;
if (n == 3) return 2;
long sum = 1;
while (n > 4) {
sum *= 3;
sum=sum%1000000007;//取模
n -= 3;
}
return (int)(sum * n % 1000000007);
}
};

0 赞同 0 条回复

普通 2023年8月3日下午11:12

c++ 代码和上一题类似
class Solution {
public:
int cuttingRope(int n)
{
long long s=1;
if(n1||n2) return 1;
if(n3) return 2;
while(n>4)
s*=3,n-=3,s%=1000000007;

       return (s*n)%1000000007;
}

};

0 赞同 0 条回复

CaCO3 永久会员 2023年8月3日上午9:45

”’java
class Solution {
public int cuttingRope(int n) {
if(n <= 3) return n – 1;
int b = n % 3, p = 1000000007;
long rem = 1, x = 3;
for(int a = n / 3 – 1; a > 0; a /= 2) {
if(a % 2 1) rem = (rem * x) % p;
x = (x * x) % p;
}
if(b 0) return (int)(rem * 3 % p);
if(b 1) return (int)(rem * 4 % p);
return (int)(rem * 6 % p);

}
”’
时间复杂度O(logn)
空间复杂度O(1)

0 赞同 0 条回复

#00456B 普通 2023年8月2日下午10:20

class Solution {
public:
    int cuttingRope(int n) {
        int mod = 1e9+7;
        if(n <= 3){
            return n - 1;
        }
        int res = n/3;
        int remain = n%3;
        if(remain == 0){
            return (pow(3, res))%mod;
        }
        else if(remain == 1){
            return (pow(3, res - 1) * 4)%mod;
        }
        else{
            return (pow(3, res) * 2)%mod;
        }
    }
    //这里用std里的pow会超出int的范围，所以需要自己定义一个long类型的pow函数
    long pow(int a, int n){
        long ans = 1;
        int mod = 1e9+7;
        while(n--){
            ans = ans*a%mod;
        }
        return ans;
    }
};

0 赞同 0 条回复

北辰普通 2023年8月2日上午11:36

class Solution {
    public int cuttingRope(int n) {
            if(n<=3) return n-1;
            int x = n/3,y=n%3;
            if(y==0) return (int) (pow(3,x)%1000000007);
            else if(y==1) return (int) (pow(3,x-1)*4%1000000007);
            else return (int) (pow(3,x)*2%1000000007);
    }

        public long pow(int a,int n) {
            long sum = 1;
            int p = 1000000007;
            for(int i=1;i<=n;i++) {
                sum = sum*a%p;
            }
            return sum;
        }
}

大数求幂，需要注意一下

0 赞同 0 条回复

Marshan 普通 2023年8月1日下午7:22

大数求幂, 以前没有留意过这类问题

class Solution {
public:
    long long cuttingRope(int n) {
        int res = n / 3;
        int mod = n % 3;
        if(n <= 3){
            return n - 1;
        }
        int p = 1000000007;
        long long sum = 0;
        if(mod == 0){
            sum = pow(3,res) % p;
        }
        else if(mod == 1){
            sum = (pow(3,res - 1) * 4) % p;
        }
        else{
            sum = (pow(3,res) * 2) % p;
        }
        return sum;
    }
    long long pow(int a,int n){
        long long sum = 1;
        int p = 1000000007;
        for(int i = 0;i < n;++i){
            sum = (sum * a) % p;
        }
        return sum;
    }
};

0 赞同 0 条回复

Mby 普通 2023年7月31日下午11:09

class Solution {
    public int cuttingRope(int n) {
        if(n <= 2){
            return 1;
        }
        if(n == 3){
            return 2;
        }

        int res = n / 3;
        int mod = n % 3;
        int p = 1000000007;

        if(mod == 0){
            return (int)pow(3, res);
        }else if(mod == 1){
            return (int)(pow(3, res - 1) * 4 % p);
        }else{
            return (int)(pow(3, res) * 2 % 1000000007);
        }
    }
    //求 a^n %p
    long pow(int a, int n){
        long res = 1;
        int p = 1000000007;
        for(int i = 1; i <= n; i++){
            res = (res * a) % p;
        }

        return res;
        //时间复杂度O(n)
        //空间复杂度O(1)
    }
}

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月30日下午9:01

class Solution {
    public int cuttingRope(int n) {
        // 可以使用动态规划
        // 也可以找规律
        // 假如将一段绳子切成两端，两端相等时，乘积最大（不等式决定）
        // 长度为1，2，3，4时都不必切，但是由于至少切成两段，所以还是得切
        // 当长度为5时，切成2*3
        // 当同时存在2，3，4时。把2，4变成3*3
        // 也就是说，要尽可能切成3
        if(n<=2) return 1;
        if(n==3) return 2;
        int res = n/3;
        int mod = n%3;
        if(mod==0) return (int)Math.pow(3,res);
        if(mod==1) return (int)Math.pow(3,res-1)*4;
        else return (int)Math.pow(3,res)*2;
    }
}

时间复杂度：本题的时间主要花在 pow 函数上，采用快速幂可以 logn 的时间复杂度
空间：O(1)

0 赞同 0 条回复

CKX 普通 2023年7月28日下午2:57

func cuttingRope(n int) int {
    if n <= 3 {
        return n-1
    }
    res := 1
    for n > 4 {
        res = res*3%1000000007
        n-=3
    }
    return res*n%1000000007
}

取余

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月27日下午9:21

7.26
Day18：下面是代码

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int b = n % 3, p = 1000000007;
        long rem = 1;  //rem,reminder,余数
        int lineNums = n / 3;  //n分为若干个3的段数
        //计算到lineNmus - 1 段。
        for(int i = 1; i < lineNums; i++){
            rem = rem * 3 % p;
        }
        if(b == 0) return (int)(rem * 3 % p);
        if(b == 1) return (int)(rem * 4 % p);
        return (int)(rem * 6 % p);
    }
}

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月26日下午9:41

代码

class Solution {
    public int cuttingRope(int n) {
        if(n<=2) return 1;
        else if(n==3) return 2;
        else{
            int res = n/3;
            int mod = n%3;
            if(mod==0){
                return (int)pow(3,res);
            }else if(mod==1){
                return (int)(pow(3,res-1)*4%1000000007);
            }else{
                return (int)(pow(3,res)*2%1000000007);
            }
        }
    }

    long pow(int a, int n){
        long res = 1;
        int p = 1000000007;
        for(int i=0;i<n;i++){
            res = (res*a)%p;
        }
        return res;
    }

}

0 赞同 0 条回复

阿尚普通 2023年7月26日下午4:51

//贪心算法
class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        long res = 1;

        while(n > 4){
            res = res * 3 % 1000000007;
            n -= 3;
        }

        return (int)(res * n % 1000000007);
    }
}

0 赞同 0 条回复

Luminous 普通 2023年7月26日下午4:31

以下是代码

class Solution {
    public int cuttingRope(int n) {
         if(n==2){
            return 1;
        }
        if(n==3){
            return 2;
        }
        if(n==4){
            return 4;
        }
        int res=n/3;
        int mod=n%3;
        int p=1000000007;
        if(mod==0){
            return (int)pow(3,res);
        }else if(mod==1){
            return (int)(pow(3,res-1)*4%p);
        }else if(mod==2){
            return (int)(pow(3,res)*2%p);
        }
        return n;
    }

    long pow(int a,int n){
        long res=1;
        int p=1000000007;
        for(int i=1;i<=n;i++){
            res=(res*a)%p;
        }
        return res;
    }
}

0 赞同 0 条回复

AD钙奶普通 2023年7月26日下午4:14

余数部分的知识还有所欠缺，看视频补了一下

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int a = n % 3, b = n / 3;
        int p = 1000000007;
        if(a == 0) {
            return (int)(pow(3,b) % p);
        }
        if(a == 1) {
            return (int)(pow(3,b-1) * 4 % p);
        }
        return (int)(pow(3,b) * 2 % p); 
    }

    public long pow(int a, int b) {
        long res = 1;
        int p = 1000000007;
        for(int i = 1; i <= b; i ++) {
            res = (res * a) % p; 
        }
        return res;
    }
}

0 赞同 0 条回复

【数学知识】剑指 Offer 14- II. 剪绳子 II

共以下 15 个回答

# 回答此问题取消回复

【数学知识】剑指 Offer 14- II. 剪绳子 II

共以下 15 个回答

# 回答此问题 取消回复

# 回答此问题取消回复