剑指 Offer 14- I. 剪绳子
力扣题目链接[1]
给你一根长度为 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
思路：
首先给出两个推论，具体的证明过程可以查看题解[2]。
- 将绳子 「以相等的长度等分为多段」 ，得到的乘积最大。
- 尽可能将绳子 「以长度 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)
。
总结
本题的题解建立在推论正确的前提下，该推论需要通过数学公式进行推导，难度系数中等。
参考资料
[1]力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5v1026/
[2]题解: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5vyva2/