淘先锋技术网

首页 1 2 3 4 5 6 7

❓剑指 Offer 14- I. 剪绳子

难度:中等

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(mn都是整数,n > 1 并且 m > 1),每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示

  • 2 <= n <= 58

注意:本题与 343. 整数拆分 相同。

💡思路:贪心

尽可能得多剪长度为 3 的绳子,并且不允许有长度为 1 的绳子出现。
(如果出现了,就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合,把它们切成两段长度为 2 的绳子。)以下为证明过程:

  • 将绳子拆成 1n-1,则 1(n-1) - n = -1 < 0,即拆开后的乘积一定更小,所以不能出现长度为 1 的绳子。
  • 将绳子拆成 2n-2,则 2(n-2) - n = n - 4,在 n >= 4 时这样拆开能得到的乘积会比不拆更大。
  • 将绳子拆成 3n-3,则 3(n-3) - n = 2n - 9,在 n >= 5 时效果更好。
  • 将绳子拆成 4n-4,因为 4=2 * 2,因此效果和拆成 2 一样。
  • 将绳子拆成 5n-5,因为 5=2+3,而 5<2*3,所以不能出现 5 的绳子,而是尽可能拆成 23
  • 将绳子拆成 6n-6,因为 6=3+3,而 6<3*3,所以不能出现 6 的绳子,而是拆成 33。这里 6 同样可以拆成 6=2+2+2,但是 3(n - 3) - 2(n - 2) = n - 5 >= 0,在 n>=5 的情况下将绳子拆成 3 比拆成 2 效果更好。
  • ...

继续拆成更大的绳子可以发现都比拆成 23 的效果更差,因此我们只考虑将绳子拆成 23,并且优先拆成 3,当拆到绳子长度 n 等于 4 时,也就是出现 3+1,此时只能拆成 2+2

🍁代码:(C++、Java)

C++

class Solution {
public:
    int cuttingRope(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        if(n == 4) return 4;
        int ans = 1;
        while(n >= 5){
            ans *= 3;
            n -= 3;
        }
        return ans * n;
    }
};

Java

class Solution {
    public int cuttingRope(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        if(n == 4) return 4;
        int ans = 1;
        while(n >= 5){
            ans *= 3;
            n -= 3;
        }
        return ans * n;
    }
}

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( l o g 3 n ) O(log3n) O(log3n)
  • 空间复杂度 O ( 1 ) O(1) O(1),只需要使用常数复杂度的额外空间。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!