LeetCode 剑指 Offer 14- II. 剪绳子 II

约 5 分钟
文章信息 8 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 剑指 Offer 剑指 Offer（第 2 版） 字节
标签
动态规划 数学

题目描述

✅ 剑指 Offer 14- II. 剪绳子 II

image-20261001230752538

题意分析

将长度为 n 的绳子剪成至少两段正整数长度，使各段长度的乘积最大，返回这个最大乘积对 1_000_000_007 的余数。取模会改变数值大小关系，因此必须先确定真正的最优切法，再计算它的模值。

解法：贪心 + 快速幂

核心思路

[!blue]

n = 2、n = 3 时必须剪开，最大乘积分别为 1、2，统一返回 n - 1。下面讨论 n > 3 的情况。

最优切法不需要长度 1：若有至少三段，将 1 与任意另一段合并，乘积会增大，段数仍不少于二；若只有 1 和 n - 1 两段，改成 2 和 n - 2 后，乘积从 n - 1 增至 2n - 4，也更大。

长度 x >= 5 的一段可以拆成 3 和 x - 3，因为 3(x - 3) > x，乘积会增大；长度 4 则可以等价拆成两个 2。因此只需考虑长度 2、3。又因为三个 2 的乘积为 8，两个 3 的乘积为 9，同样用掉长度 6 时后者更优，所以 2 最多保留两段，其余尽量使用 3。

按 n 除以 3 的余数确定结果：余 0 时全用 3；余 2 时保留一段 2；余 1 时不能留下 1，要撤回一段 3，与这个 1 合成两段 2。这样乘积统一写成 3^a * b，其中 a 是长度为 3 的段数，b 是剩余因子 1、2 或 4。

快速幂按指数的二进制位计算 3^a：res 保存已选幂的乘积，cur 依次代表指数权重为 1、2、4 等的幂。当前指数为奇数说明最低位为 1，把 cur 乘入 res；随后将 cur 平方、指数右移一位。所有位处理完后，res 就是所需幂值，每次乘法都立即取模。

解题步骤

  • n <= 3 时返回 n - 1，处理必须至少剪一刀的限制。
  • 令 a = n / 3、b = n % 3。余 1 时将 a 减 1、b 设为 4；余 0 时将 b 设为乘法单位元 1；余 2 保持不变。
  • 快速幂从 res = 1 开始，逐位计算 3^a 的模值。
  • 将幂值与 b 相乘后再次取模。n = 4 时指数为 0，幂函数直接返回 1，最终得到两段 2 的乘积。

代码实现

// 余一时把三与剩下的一改成二加二。
class Solution {
    private static final int MOD = 1_000_000_007;

    public int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }

        int a = n / 3;
        int b = n % 3;

        if (b == 1) {
            // 余一时撤回一段三，把三与一改成两个二。
            a--;
            b = 4;
        } else if (b == 0) {
            // 没有剩余长度，乘法因子使用单位元一。
            b = 1;
        }

        long pow = fastPow(3, a);

        return (int) (pow * b % MOD);
    }

    private long fastPow(long base, int exp) {
        long res = 1;
        long cur = base % MOD;
        int e = exp;

        while (e > 0) {
            if ((e & 1) == 1) {
                res = res * cur % MOD;
            }

            // 宽整数乘法后取模，保持后续乘积处在可表示范围。
            cur = cur * cur % MOD;
            e >>= 1;
        }

        return res;
    }
}

// 余一时把三与剩下的一改成二加二。
func cuttingRope(n int) int {
    const mod int64 = 1_000_000_007
    if n <= 3 {
        return n - 1
    }

    a := n / 3
    b := n % 3
    if b == 1 {
        // 余一时撤回一段三，把三与一改成两个二。
        a--
        b = 4
    } else if b == 0 {
        // 没有剩余长度，乘法因子使用单位元一。
        b = 1
    }

    pow := fastPow(3, a, mod)
    return int(pow * int64(b) % mod)
}

func fastPow(base int64, exp int, mod int64) int64 {
    res := int64(1)
    cur := base % mod
    for exp > 0 {
        if exp&1 == 1 {
            res = res * cur % mod
        }
        // 宽整数乘法后取模，保持后续乘积处在可表示范围。
        cur = cur * cur % mod
        exp >>= 1
    }
    return res
}

复杂度分析

  • 时间复杂度：$O(\log(n+1))$。确定切法只需常数操作，快速幂每轮将指数减半。
  • 空间复杂度：$O(1)$。只保存商、余数和快速幂的几个状态。

关键点总结

[!green]

  • 先排除 1 和大于 4 的段，再比较三个 2 与两个 3，得到尽量使用 3 的规律。
  • 余 1 时使用两段 2，不是保留长度 1。
  • 快速幂计算的是已确定最优乘积的模值，取模不参与选择切法。

易错点总结

[!yellow]

  • 小于等于 3 时不能返回原长度，因为题目要求至少剪成两段。
  • 余 1 时改成因子 4，也必须同步少算一个 3，否则总长度会超过 n。
  • 余 0 时剩余因子应为 1，设为 0 会把整个乘积清零。
  • 指数为 0 时应返回 1；快速幂的累乘初值不能为 0。
  • 模乘前保留 long / int64，乘完再取模，不能先转成窄整数，也不能用浮点幂计算大整数结果。

相似题目

题目 难度 关联与区别
343. 整数拆分 中等 最优拆分规律相同，本题范围更大并要求取模，不能按模后的大小决定切法。
50. Pow(x, n) 中等 快速幂的二进制分解可复用，但本题需要整数模乘版本，不能直接浮点pow后取模。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/33302047
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！