剑指Offer题解 - Day53

剑指 Offer 14- I. 剪绳子

力扣题目链接 (opens new window)

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

示例 1:

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

提示：

• 2 <= n <= 58

思路：

首先给出两个推论，具体的证明过程可以查看题解 (opens new window)。

• 将绳子 以相等的长度等分为多段 ，得到的乘积最大。
• 尽可能将绳子 以长度 3 等分为多段时，乘积最大。

通过以上推论，我们应该如此切分绳子：

• 将绳子切分为长度为3的片段，如果可以完全切分，那么就求出了最优方案。如果不能完全切分，则剩余绳子长度为1和2。
• 当剩余绳子长度为2时，不再进行切分。
• 当剩余绳子长度为1时，则应该将长度3和长度1替换为长度2和长度2，因为 2 * 2 > 3 * 1。

根据以上逻辑分析，可以写出如下代码：

/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function(n) {
    if (n <= 3) return n - 1;
    let a = Math.floor(n / 3);
    let b = n % 3;
    if (b === 0) return Math.pow(3, a);
    else if (b === 1) return Math.pow(3, a - 1) * 4;
    else return Math.pow(3, a) * 2;
};

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

分析：

根据题目要求，必须至少剪一刀，因此当n等于2或者3的时候，剪出一根长度为1的绳子，剩下的绳子长度就是最大的，也就是(n - 1) * 1 ，直接返回n - 1即可。

其余代码分别处理了绳子分为多段长度为3的片段后，剩余绳子长度是0、1、2的情况。

复杂度方面，仅有向下求整、求余、次方运算，因此时间复杂度是O(1) 。变量a、b占用常数级别空间，因此空间复杂度是O(1) 。

总结

本题的题解建立在推论正确的前提下，该推论需要通过数学公式进行推导，难度系数中等。