九号球普通 2023年11月22日下午9:01

“`java
//数学是基础
class Solution {
public int cuttingBamboo(int bamboo_len) {
if(bamboo_len <= 3) { return bamboo_len - 1; } int remainder = bamboo_len % 3; int count3 = bamboo_len/3; if (remainder == 1) { count3--; } int p = 1000000007; long res = 1; while(count3 > 0) {
res = (res * 3)%p;
count3–;
}
if (remainder == 1) {
res = (res * 4)%p;
} else if (remainder == 2) {
res = (res * 2)%p;
}
return (int)res;
}

}

0 赞同 0 条回复

招舟子普通 2023年9月7日下午3:02

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

    int p = 1000000007;
    long result = 1;
    while (n > 4) {
        result = (result * 3) % p;
        n -= 3;
    }
    return (int) (result * n % p);
}

}
大树求余

0 赞同 0 条回复

怀瑾永久会员 2023年7月19日下午3:29

“`C++
const int mod = 1e9 + 7;
int cuttingRope(int n) {
vector dp(n + 1, 0);
dp[2] = 1; // 初始化，当绳子长度为 2 时只有一种剪法，剪成两段长度都为 1

for (int i = 3; i <= n; ++i) {
    for (int j = 1; j <= i / 2; ++j) {
        dp[i] = max(dp[i], max((j * (i - j)) % mod, (dp[j] * (i - j)) % mod));
    }
}

return dp[n] % mod;

}

“`

0 赞同 0 条回复

憨憨永久会员 2023年7月18日下午1:27

数学推到加上大数运算

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

        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 % p);
        }else{
            return (int)(pow(3, res) * 2 % p) ;
        }
    }
    private long pow(int a, int b){
        long ans = 1;
        for(int i = 0; i < b; i ++){
            ans = (ans * a) % p;
        }
        return ans ;
    }
}

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月16日下午8:25

模

class Solution {
    public int cuttingRope(int n) {
        if(n==2)
            return 1;
        if(n==3)
            return 2;
        if(n==4)
            return 4;
        long res=1L;
        while(n>4){
            n-=3;
            res=res*3%1000000007;
        }
        res=res*n%1000000007;
        return (int)res;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月16日上午10:14

java
class Solution {
    public int cuttingRope(int n) {
        /*
            分成等分的话乘积最大，1,2,3,4不可再拆分，拆分段长度为3是最优的，对3取模后余数为0或1或2,
            1加到3里面形成4,2直接相乘
            增加了大数取模的步骤，可用循环取余法和二分取余法
        */
        if(n <= 2) {
            return 1;
        }
        if(n == 3) {
            return 2;
        }

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

        if(mod == 0) {
            res = (int)pow(3, res, p);
        } else if(mod == 1) {
            res = (int)(pow(3, res - 1, p) * 4 % p) ;
        } else {
            res = (int)(pow(3, res, p) * 2 % p);
        }
        return res;
    }
    //循环取余法，时间复杂度是o(n)
    public long pow(int a, int x, int p) {
        long result = 1;
        for(int i = 1; i <= x; i++) {
            result = (result * a) % p;
        }
        return result;
    }
}

时间复杂度是O(N), 空间复杂度是O(1)

0 赞同 0 条回复

BOZ 普通 2023年7月15日下午3:10

【思路】总体思路与剪绳子1类似，需要加上mod处理：(ab)%x = ((a%x)(b%x))%x
【复杂度】时间复杂度O(n)，空间复杂度O(1)

class Solution {
    const int limit = 1000000007;
    long pow(int a, int b) {
        long res = 1;
        for(int i= 0; i < b; i++)
            res = (res * a) % limit;
        return res;
    }
public:
    int cuttingRope(int n) {
        if (n < 4) return n - 1;

        int mod = n % 3;
        if (mod == 1) return pow(3, n / 3 - 1) * 4 % limit;
        else if (mod == 2) return pow(3, n / 3) * 2 % limit;
        else return pow(3, n / 3) % limit;
    }
};

0 赞同 0 条回复

花老爷普通 2023年7月14日下午9:47

根据剪绳子1的结论，加上mod处理
时间：O(n)
空间：O(1)

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

0 赞同 0 条回复

江畅普通 2023年7月13日上午11:00

// 剪绳子
// 时间复杂度 O(N)
// 空间复杂度 O(1)
class Solution {
private:
    long pow(int a, int n) {
        long res = 1;
        int p = 1'000'000'007; 
        for (int i = 1; i <= n; ++i) {
            res = res * a % p;
        }
        return res;
    }

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 = 1'000'000'007;

        if (mod == 0) { return pow(3, res) % p; }
        else if (mod == 1) { return pow(3, res - 1) * 4 % p; }
        else { return pow(3, res) * 2 % p; }
    }
};

0 赞同 0 条回复

Dsjh 普通 2023年7月10日下午5:45

MY

帅弟

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)pow1(3,res);
        }
        else if(mod == 1){
            return (int)(pow1(3,res-1)*4 % p);
        }
        else{
            return (int)(pow1(3,res)*2 % p);
        }
        return 0;
    }
    long pow1(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月9日下午10:22

时间复杂度：O(n)
空间复杂度：O(1)

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

        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 % p);
        } else {
            return (int) (pow(3, res) * 2 % p);
        }
    }

    public long pow(int x, int n){
        long sum = 1;

        for(int i = 0; i < n; i++){
            sum = (sum*x) % p;
        }
        return sum;
    }
}

0 赞同 0 条回复

Ming 普通 2023年7月9日下午4:21

公式a^n % p = (a^(n-1)%p * a) %p
时间复杂度：O(n)
空间复杂度：O(1)

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 %p);
        }
    }
    // 求a^n % p = (a^(n-1)%p * a) %p
    public 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 条回复

小吕普通 2023年7月9日下午2:17

c++实现
int cuttingRope(int n) {
if(n<2)return 0;
if(n2) return 1;
if(n3) return 2;
int x = n/3;
int ll = n%3;
int mm=1000000007;
if(ll0)
{
return pow(3,x)%mm;
}
else if(ll1)
{
return pow(3,x-1)4%mm;
}
else return pow(3,x)2 %mm;
}
long pow(int x,int n)
{
long res = 1;
int mm = 1000000007;
for(int i = 0;i<n;i++)
{
res = (res*x)%mm;
}
return res;
}

0 赞同 0 条回复

Vow the vow。普通 2023年7月9日下午2:09

public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int b = n % 3, p = 1000000007;

        long rem = 1, x = 3 ,a = n / 3;
        //直接套循环求余公式
        for(int i = 0; i < ((b == 1)?a-1:a); i++) { //b == 1代表余数为1的时候，需要单独取出一个3出来凑成2*2达到最大值效果
            rem = (rem * x) % p;
        }  
        if(b == 0) return (int)(rem % p);
        if(b == 1) return (int)(rem * 4 % p);
        return (int)(rem * 2 % p);
    }

0 赞同 0 条回复

张开怀普通 2023年7月9日下午12:22

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 pow(3,res) % p;
              }else if(mod == 1){
                     return (pow(3,res-1) *4) % p;
              }else{
                     return (pow(3,res)*2)%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月8日下午11:07

// 时间O(n),空间O(1)
class Solution {
public:
    int cuttingRope(int n) {
        if(n<=3) return n-1;
        int res = n/3;
        int mod = n%3;
        int tmp = 1e9+7;
        long ans=1;
        for(int i =1;i<res;++i)
        {
            ans = (ans*3)%tmp;
        }
        if(mod==0) return (int)(ans*3%tmp);
        else if(mod==1) return (int)(ans*4%tmp);
        else return (int)(ans*2*3%tmp);  //*和%优先级相同
    }
};

0 赞同 0 条回复

局外人普通 2023年7月8日下午10:59

思路：根据数学性质，将绳子每段剪成离e最近的整数3即可最大，通过迭代到只剩下>4的长度，最后一段直接乘以累积数值
时间复杂度：O(logn) 空间复杂度：O(1)

class Solution {
    public int cuttingRope(int n) {
        if(n<4) return n-1;
        long res = 1L;
        while(n>4){
            res = (res*3)%1000000007;
            n = n - 3;
        }
        return (int)((res * n)%1000000007);
    }
}

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月8日下午10:52

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[2] = 1

        for i in range(3, n + 1):
            for j in range(1, i // 2 + 1):
                dp[i] = max(dp[i], max(dp[i - j] * j, (i - j) * j))

        return dp[n]

动态规划

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月8日下午9:09

//时间O(n) 空间O(n)

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

        int count = n / 3;  //  能分成几个3
        int remainder = n % 3;
        int result = 0;

        if(remainder == 0){
            result =  (int)(pow(3,count) % 1000000007);
        }
        if(remainder == 1){
            //凑成四
            result =  (int)(pow(3,count - 1) * 4 % 1000000007);
        }
        if(remainder == 2){
            result =  (int)(pow(3,count) * 2 % 1000000007);   
        }

        return result ;
    }

    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 条回复

伏月三十普通 2023年7月8日下午6:23

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%p);
        }
    }
    //求a^n 大数取余的思想
    private 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 条回复

Yodl. 普通 2023年7月8日下午2:47

//找规律
const int p = 1000000007;
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;

        if (mod == 0) {
            return pow(3, res) % p;
        } else if (mod == 1) {
            return (pow(3, res - 1) * 4) % p;
        } else {
            return (pow(3, res) * 2) % p;
        }
    }

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

        return res;
    }
};

0 赞同 0 条回复

yxy 普通 2023年7月8日下午2:24

复杂度O(n)

const int m = 1e9+7;
class Solution {
public:
    int cuttingRope(int n) {
        if(n==2) return 1;
        if(n==3) return 2;
        if(n==4) return 4;
        long res = 1;
        while(n>4)
        {
            n-=3;
            res*=3;
            res%=m;
        }
        res*=n;
        res%=m;
        return res;
    }
};

0 赞同 0 条回复

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

共以下 22 个回答

MY

# 回答此问题取消回复

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

共以下 22 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复