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

Sheng 永久会员 2023年9月13日下午8:29

看的答案做的，
‘“java
public int cuttingRope(int n) {
if(n 2) return 1;//长度为2的绳子只能剪1和1
if(n 3) return 2;//长度为3的绳子剪1和2

    //看leetcode的解析
    //分成3的长度，乘积是最大的
    //剩下的单独处理，余数为0不用管；余数为1，拉一个3分成2+2，1*3<2*2;余数为2直接相乘
    int a = n / 3;//分成多少份
    int b = n % 3;//剩下多少
    if(b == 0) {
        return (int)(Math.pow(3, a));
    }
    else if(b == 1) {
        return (int)(Math.pow(3, a-1) * 2 * 2);
    }
    else {
        return (int)(Math.pow(3, a) * 2);
    }


}

“`

0 赞同 0 条回复

sc_Yang 普通 2023年9月10日下午10:26

// 先上结论：将绳子等分会使得结果最大。
// 并且等分的长度为3时，结果乘积最大。
class Solution {
public:
    int cuttingRope(int n) {
        if(n==1) return 1;
        if(n==2) return 1;
        if(n==3) return 2;
        if(n==4) return 4;
        int res=1;
        while(n>4){
            res = res * 3;
            n = n-3;
        }
        res = res * n;
        return res;
    }
};

0 赞同 0 条回复

小肸永久会员 2023年9月7日下午3:39

class Solution {
    public int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        //贪心：每一个大于4的数字可以拆分成两个数的乘积大于4
        //所以需要拆分的长度尽可能是2、3
        //但3^2=9,而2^3=8,所以需要尽可能地拆分3
        //最后4是拆分为3、1还是2、2，是2、2，因为3*1 < 2 * 2。
        //时间和空间复杂度应该是O(1)，Math.pow()应该是O(1)，Java是调用native()方法计算pow
        int quantity = n / 3;
        int remainder = n % 3;
        if (remainder == 0) {
            return (int)Math.pow(3, quantity);
        } else if (remainder == 1) {
            return (int)Math.pow(3, quantity - 1) * 4;
        } else {
            return (int)Math.pow(3, quantity) * 2;
        }
    }
}

0 赞同 0 条回复

sincere 普通 2023年9月5日下午4:45

思路：数学推导，2和3没必要再拆分，大于等于4的，拆成越多个3或者2，乘积越大
复杂度：时间复杂度O(1)，空间复杂度O(1)

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

0 赞同 0 条回复

塔底的仰望永久会员 2023年9月3日上午11:01

使用了快速幂算法计算，时间复杂度O(n)

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);
       } else if (mod == 1) {
           return pow(3,res - 1) * 4;
       } else {
           return pow(3, res) * 2;
       }
    }

    public int pow(int a, int n) {
        int sum = 1;
        int temp = a;
        while (n > 0) {
          if ((n&1) == 1) {
              sum *= temp;
          } 
          temp *= temp;
          n = n >> 1; 
        }
        return sum;
    }
}

0 赞同 0 条回复

c 普通 2023年9月1日上午10:39

根据题解学习数学

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

0 赞同 0 条回复

别扒拉我普通 2023年8月31日下午11:46

分享一个dp思路

public int cuttingRope(int n) {
        // f(0)=1,f(1)=1,f(2)=1*1,f(3)=2
        if (n <= 3) {
            return Math.max(n - 1, 1);
        }
        // dp思路：砍成两段的最大乘积是 f(n) = f(x)*f(n-x)
        // f(2)虽然=1，在计算的时候的等于2，比如4=2*2=4,不能是1*1
        // f(3)虽然=2，在计算的时候的等于3，比如6=3*3=9,不能是2*2
        // 也就是说在dp计算的时候,f(x)的最小值只能是x,不能小于x
        // 在x>=4的时候计算出来都是大于x,所以不需要特殊定义
        int[] f = new int[n + 1];
        f[1] = 1;
        f[2] = 2;
        f[3] = 3;
        int ans = 1;
        for (int i = 4; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {
                ans = Math.max(ans, f[j] * f[i - j]);
            }
            f[i] = ans;
            ans = 0;
        }
        return f[n];
    }

0 赞同 0 条回复

JustRtn 普通 2023年8月31日下午3:17

时空复杂度O(1)

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

    long power(unsigned int base, int n) {
        long result = 1;
        while (n > 0) {
            if (n & 1) {
                result *= base;
            }
            base *= base;
            n >>= 1;
        }
        return result;
    }
};

0 赞同 0 条回复

行动派小彩笔普通 2023年8月31日下午2:18

//数学思想，时间复杂度O(1),空间复杂度O(1)
class Solution {
public:
    int cuttingRope(int n) {
        if(n<=3) return n-1;

        int val1 = n/3;
        int val2 = n%3;
        if(val2 == 1) return pow(3,val1-1)*4;
        else if(val2==2) return pow(3,val1)*2;

        return pow(3,val1);
    }
};

0 赞同 0 条回复

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

共以下 9 个回答

# 回答此问题取消回复

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

共以下 9 个回答

# 回答此问题 取消回复

# 回答此问题取消回复