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

Categories:

题目描述
思路分析
1. 解法一：贪心 + 快速幂（推荐）
相似题目

题目描述

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

思路分析

解法一：贪心 + 快速幂（推荐）

核心思路：

当 n > 3 时，优先切 3 能最大化乘积。

若余数为 1，则把一个 3 改成 2+2。

大数取模，用快速幂计算 3 的指数。

复杂度分析：

时间复杂度：O(log n)。

空间复杂度：O(1)。

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
}

相似题目

题目	难度	考察点
343. 整数拆分	中等	贪心
264. 丑数 II	中等	数学
370. 区间加法	中等	数学
793. 阶乘函数后 K 个零	困难	数学
279. 完全平方数	中等	数学

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/33302047