题解 | #剪绳子（进阶版）#

JZ83 剪绳子（进阶版）

题目描述

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

方法一：暴力算法

解题思路

对于求乘积的最大值，我们很容易想到，当每个因子接近的时候，得到的结果最大。

上述理由为根据均值不等式有：

当a1=a2=...=an时等号成立，此时取得最大。

如果将绳子按照每段长度为x，等分成m段，则n=mx，题目所要求的结果为$x^{m}x^m$，因为有$x^{m}x^m$= x^(n/x)，所以当x^(1/x)取得最大时，即可得到所求的最大值。对x^(1/x)进行取对数，再求导，可以得知其取到整数最大值时，x的值为3，于是我们对于本题的求解时尽量将绳子分割的段数凑为三，最后我们直接使用暴力算法进行输出。

解题代码

class Solution {
public:
    long long cutRope(long long number) {
        if(number <= 3) //不超过3直接计算
            return number - 1;
        long x = 1;
        // 暴力算法
        while(number > 4)
        {
            x *= 3;
            x = x % 998244353;
            number -= 3; 
        }
        return x * number % 998244353;
    }
};

复杂度分析

时间复杂度：n为绳子长度，因为绳子长度都需要遍历，因此时间复杂度为$O(N)O(N)$。

空间复杂度：无额外内存地址空间，因此空间复杂度为$O(1)O(1)$

方法二：快乘方法

解题思路

对于快速乘法，其简单的理解为a * b = a * (b1 +b2+...+bn)。其把乘法用加法进行代替，使得计算更快。对于本题目，其分割绳子并计算乘积的最大值，即是求幂的最大值，我们有如下图进行幂次求解展示，并通过图例说明快乘的使用方法。

解题代码

public class Solution {
    public long pow (long cnt) 
    {   //计算幂值
        if (cnt == 0) return 1;
        if (cnt == 1) return 3;
        long part = pow(cnt / 2);
        if (cnt % 2 == 0) return part * part % 998244353;
        return 3 * part * part % 998244353;
    } 
    public long cutRope (long number) {
        // write code here
        if (number == 2) return 1;
        if (number == 3) return 2;
        long cnt = number / 3;
        if (number % 3 == 0)
        {
            return pow(cnt) % 998244353;// 情况1
        }
        else if (number % 3 == 1)
        {
            cnt--;
            return 2 * 2 * pow(cnt) % 998244353;// 情况2
        }
        else
        {
            return 2 * pow(cnt) % 998244353;// 情况3
        }
    }
}

复杂度分析

时间复杂度：相当于二分法，因此时间复杂度为$O(logN)O(logN)$

空间复杂度：没有使用额外的内存地址空间，因此空间复杂度为$O(1)O(1)$