劍指 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/