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

=.= 普通 2024年4月5日下午10:09

class Solution {
public int cuttingBamboo(int bamboo_len) {
int n = bamboo_len;

    if(n <= 1) return n;
    if(n <= 3) return 2;
    int[] ans = new int[n+1];

    for(int i=1; i<n+1; i++){
        ans[i] = i;
    }
    for(int i=5; i<n+1; i++){
        for(int j=1; j<=i/2; j++){
            ans[i] = Math.max(ans[i], ans[j] * ans[i-j]);
        }
    }

    return ans[n];
}

}
时间：O(n2)
空间：O(n)

0 赞同 0 条回复

kfaebot 普通 2024年3月27日下午3:38

class Solution {
public:
    int cuttingBamboo(int bamboo_len) {
        //特殊情况
        if(bamboo_len<=3){
            return bamboo_len-1;
        }
        int a=bamboo_len/3;
        int b=bamboo_len%3;
        if(b==0){
            return pow(3,a);
        }
        else if(b==1){
            return pow(3,a-1)*4;
        }
        else if(b==2){
            return pow(3,a)*2;
        }
        return 0;
    }
};

0 赞同 0 条回复

NULL 普通 2024年3月26日下午4:03

class Solution {
public int integerBreak(int n) {
if (n <= 2) return 1;
if (n 3) return 2;
int res = n / 3;
int mod = n % 3; // 尽可能分成长度为3的res段
if (mod 0) { // 正好拆分为整数个3
return (int)Math.pow(3, res);
} else if (mod 1) {
return (int)(Math.pow(3, res – 1) * 4);
} else {
return (int)(Math.pow(3, res) * 2);
}
}
}

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月23日下午8:05

class Solution {

    // 普通方法
    // long pow(int a, int n){
    //     long res = 1;
    //     for(int i = 1; i <= n; i++){
    //         res = res * a;
    //     }
    //     return res;
    // }

    //快速幂方法
    long pow(int a, int n){
        long res = 1;
        long y=n;
        long temp=a;

        while(y>0){
            if((y&1)==1){
                res*=temp;
            }
            temp*=temp;
            y=y>>1;
        }
        return res;
    }

    public int cuttingBamboo(int bamboo_len) {

        int n = bamboo_len;

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

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

0 赞同 0 条回复

方铎码农普通 2024年3月23日下午4:45

class Solution {
    public int cuttingBamboo(int bamboo_len) {
        if(bamboo_len <= 3) {
            return bamboo_len - 1;
        }
        int quoient = bamboo_len / 3;
        int remainder = bamboo_len % 3;
        if(remainder == 0){
            //余数为0，bamboo_len = 3m, bamboo切分为m个3
            return (int)Math.pow(3, quoient);
        } else if (remainder == 1) {
            return (int)Math.pow(3, quoient-1)*4;
        } else {
            return (int)Math.pow(3, quoient)*2;
        }
    }
}

时间复杂度$O(1)$，空间复杂度$O(1)$

0 赞同 0 条回复

神经蛙普通 2024年3月22日下午11:41

class Solution {
public:
int cuttingBamboo(int bamboo_len) {
if(bamboo_len <= 3) return bamboo_len -1;
int a = bamboo_len /3;
int b = bamboo_len %3;
if(b 0) return pow(3, a);
if(b 1) return pow(3, a-1)4;
return pow(3, a)2;
}
};
时间复杂度和空间复杂度都是Ｏ（１）

0 赞同 0 条回复

紫芝普通 2024年3月22日下午12:31

思路：数学推导

func cuttingBamboo(bamboo_len int) int {
    if bamboo_len <= 3 { return bamboo_len - 1 }
    quotion, remainter := bamboo_len / 3, bamboo_len % 3
    if remainter == 0 {
        return int(math.Pow(3, float64(quotion)))
    }
    if remainter == 1 {
        return int(math.Pow(3, float64(quotion)-1) * 4)
    }
    return int(math.Pow(3, float64(quotion)) * 2)
}

0 赞同 0 条回复

mpweixin用户普通 2024年3月21日下午11:15

public int cuttingBamboo(int bamboo_len) {
if(bamboo_len<=3) return bamboo_len-1;
int a=bamboo_len/3,b=bamboo_len%3;
if(b0) return (int)Math.pow(3,a);
if(b1) return (int)Math.pow(3,a-1)4;
return (int)Math.pow(3,a)2;
}
思路：数学问题均值不等式和函数求导确定

0 赞同 0 条回复

mpweixin用户普通 2024年3月21日下午9:59

java
class Solution{
public int cuttingBamboo(int bamboo_len){
if(bamboo_len <= 3) return bamboo_len – 1;
int a = bamboo_len / 3, b = bamboo_len % 3;
if(b 0) return (int)Math.pow(3, a);
if(b 1) return (int)Math.pow(3, a – 1) * 4;
return (int) Math.pow(3, a) * 2;
}
}
提交

0 赞同 0 条回复

机电皮怪永久会员 2024年3月21日下午8:46

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

“`C++
class Solution {
public:
int cuttingBamboo(int bamboo_len) {
if( bamboo_len < 4 ) { return bamboo_len - 1; } int a = bamboo_len/3; int b = bamboo_len%3; if(b == 0) { return pow(3, a); } if(b == 1) { return pow(3, a - 1) * 4; } return pow(3, a) * 2; } }; ```

0 赞同 0 条回复

Jimmy 普通 2024年3月21日下午8:05

class Solution {
public:
    int cuttingBamboo(int bamboo_len) {
        if(bamboo_len>3){
            int a = bamboo_len/3, b = bamboo_len%3;
            switch(b){
                case 0: return pow(3,a);
                case 1: return pow(3,a-1)*4;
                case 2: return pow(3,a)*2;
            }
        }
        return bamboo_len-1;// bamboo_len<=3,绳子必须被切割，长度为2的时候，被切割为1*1,长度为3的时候，被切割为1*2
    }
};

0 赞同 0 条回复

一个达不刘普通 2024年3月21日下午5:37

class Solution {
public:
int cuttingBamboo(int bamboo_len) {
//dp[i] 表示将正整数 i拆分成至少两个正整数的和之后，这些正整数的最大乘积。
vector dp(bamboo_len +1);
for(int i=2; i<=bamboo_len;i++){
int curMax = 0;
for(int j =1;j<i;j++){//从1开始拆分，
curMax = max(curMax, max(j(i-j), jdp[i-j]));
}
dp[i] = curMax;

    }
    return dp[bamboo_len];

}

};

0 赞同 0 条回复

heathhou 普通 2024年3月21日下午3:38

class Solution {
public:
    int cuttingBamboo(int bamboo_len) {
        // 绳子必须被切割，长度为2的时候，被切割为1*1
        if( bamboo_len <= 2){
            return 1;
        // 绳子必须被切割，长度为3的时候，被切割为1*2
        }else if( bamboo_len == 3){
            return 2;
        }

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

0 赞同 0 条回复

Raphtalia. 普通 2024年3月21日下午2:19

class Solution {
public:
int cuttingBamboo(int bamboo_len) {
if(bamboo_len <= 3) return bamboo_len – 1;
int x = bamboo_len / 3, y = bamboo_len % 3;
if(y 0) return pow(3, x);
if(y 1) return pow(3, x – 1) * 4;
return pow(3, x) * 2;
}
};时间复杂度O(1),

0 赞同 0 条回复

云无深雁影普通 2024年3月21日上午11:20

class Solution {
public int cuttingBamboo(int bamboo_len) {
//dp
int[] dp = new int[bamboo_len + 1];
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i < bamboo_len+1; i++){
int maxLen = 0;
for(int j = 1; j < i; j++){
maxLen = Math.max(maxLen,Math.max(j*(i-j),j * dp[i – j]));
}
dp[i] = maxLen;
}

    return dp[bamboo_len];

}

}//方法一 dp 时间复杂度On2 空间复杂度On

class Solution {
public int cuttingBamboo(int bamboo_len) {
if(bamboo_len <= 3)
return bamboo_len – 1;
int v1 = bamboo_len % 3;
int v2 = bamboo_len / 3;
if(v1 0)
return (int) Math.pow(3,v2);
else if(v1 1)
return (int) Math.pow(3,v2 – 1)*4;
return (int) Math.pow(3,v2) * 2;
}
}//数学法时间复杂度O1 空间复杂度O1

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月21日上午8:27

打卡

class Solution {
public:
    int cuttingBamboo(int bamboo_len) {
        if(bamboo_len == 2) return 1;
        if(bamboo_len == 3) return 2;

        int res = 0;
        int mod = bamboo_len % 3;
        int cnt = bamboo_len / 3;
        if(mod == 0) res = pow(3, cnt);
        else if(mod == 1) res = pow(3, cnt - 1) * 4;
        else res = pow(3, cnt) * 2;
        return res;
    }
};

0 赞同 0 条回复

Yox 普通 2024年3月21日上午1:42

class Solution:
def cuttingBamboo(self, bamboo_len: int) -> int:
if bamboo_len <= 3: return bamboo_len – 1
a, b = bamboo_len // 3, bamboo_len % 3
if b 0: return int(math.pow(3, a))
if b 1: return int(math.pow(3, a – 1) * 4)
return int(math.pow(3, a) * 2)

关于为什么切分为3的优先级最高可以利用均值不等式求出乘积最大值 L(m)=(n/m)^m 对此式求导（可利用对数法），可以证明当 m=n/e 时，乘积取最大，此时每段绳子的长度为 n/(n/e)=e，自然对数e的值为2.718，显然接近3，所以总体来讲3最好

0 赞同 0 条回复

MARS 普通 2024年3月20日下午11:31

/**
 * @param {number} bamboo_len
 * @return {number}
 */
var cuttingBamboo = function (bamboo_len) {
    if (bamboo_len <= 3) {
        return bamboo_len - 1
    }

    let q = Math.floor(bamboo_len / 3) //分几段
    let r = bamboo_len % 3  //余1还是2
    if (r == 0) {
        return Math.pow(3, q);   //无余数，直接幂次
    } else if (r == 1) { 
        return Math.pow(3, q - 1) * 4; //余1，加到一个3上
    } else {
        return Math.pow(3, q) * 2;   //余2，乘以2
    }

}

0 赞同 0 条回复

南梁陈庆之普通 2024年3月20日下午10:14

时间复杂度O（N2）
空间复杂度O（N）

class Solution {
    public int cuttingBamboo(int bamboo_len) {
        int[] dp = new int[bamboo_len + 1];
        for (int i = 2; i <= bamboo_len; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                curMax = Math.max(curMax, Math.max(j * (i - j) , j * dp[i - j]));
            }
            dp[i] = curMax;

        }
        return dp[bamboo_len];
    }
}

0 赞同 0 条回复

言之命至普通 2024年3月20日下午10:06

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){ //正好是3的倍数
            return pow(3, res);
        } else if(mod == 1){ //余数为1，把1加到一个3里面
            return pow(3, res - 1) * 4;
        } else {//余数为2，相乘
            return pow(3, res) * 2;
        }
    }
    int pow(int a, int n){
        int sum = 1;
        for(int i = 1; i <= n; i ++){
            sum = sum * a;
        }
        return sum;
    }

0 赞同 0 条回复

王位詮釋普通 2024年3月20日下午9:13

帅地的公式解法：
class Solution {
    int result = 1;
    int max = 0;
    int count = 1;
    public int cuttingBamboo(int bamboo_len) {
        if(bamboo_len<2){
            return 1;
        }
        if(bamboo_len==3){
            return 2;
        }
        int res = bamboo_len/3;
        int mod = bamboo_len%3;
        if(mod==0){
            return pow(3,res);
        }else if(mod == 1){
            return pow(3,res-1)*4;
        }else{
            return pow(3,res)*2;
        }
    }
    public int pow(int n,int m){
        int result = 1;
        for(int i = 0;i<m;i++){
            result*=n;
        }
        return result;
    }
}

自己本来想用回溯法来解的 但是如果bamboo_len比较大的时候（28），这时候直接超时了，但是在idea里能输出正确答案，不过idea里也会稍微卡一下才出答案，可能是因为没剪枝的问题，这里还是记录一下回溯：
public class Solution {
        int result = 1;
        int max = 0;
        int count = 1;
        public int cuttingBamboo(int bamboo_len) {
            backtrace(bamboo_len);
            return max;
        }

        public void backtrace(int bamboo_len){
            if(bamboo_len<1){
                if(max<result){
                    max = result;
                }
                return;
            }
            for(int i = 1;i<=bamboo_len;i++){
                if(i==bamboo_len&&count==1){
                    break;
                }
                result*=i;
                count++;
                backtrace(bamboo_len-i);
                result/=i;
                count--;
            }
        }
}

0 赞同 0 条回复

【数学专题】剑指 Offer 14- I. 剪绳子

共以下 21 个回答

# 回答此问题取消回复

【数学专题】剑指 Offer 14- I. 剪绳子

共以下 21 个回答

# 回答此问题 取消回复

# 回答此问题取消回复