剑指offer - 剪绳子 II - JavaScript

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

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

提示:2 <= n <= 1000

# 题目分析

本题的求解思路和LeetCode 343.整数拆分几乎一样,有动态规划和贪心法两种解法,具体请看这篇文章:《LeetCode 343.整数拆分 - JavaScript》

# 解法:过程中取模

和 Leetcode343 不同的是,本题中的 n 的取值范围很大,需要对结果进行取模。以贪心法的思路为例,如果直接计算 n 中 3 的个数 a,然后计算 3 的 a 次方,最后再取模,那么可能会出错。

正确的做法是:利用取模运算的性质,在过程中对每一步结果取模,这样保证每一步结果都不会溢出。

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/
// 原文地址:https://xxoo521.com/2020-02-15-jian-sheng-zi-ii-lcof/

/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function (n) {
  if (n <= 3) return n - 1;

  let res = 1;
  while (n > 4) {
    n -= 3;
    res = (res * 3) % 1000000007;
  }
  return (n * res) % 1000000007;
};

时间复杂度是$O(N)$,空间复杂度是$O(1)$。

# 更多资料