LeetCode 剑指 Offer 14- I. 剪绳子

Categories:

题目描述
思路分析
1. 解法一：贪心切 3（推荐）
相似题目

题目描述

✅ 剑指 Offer 14- I. 剪绳子

思路分析

解法一：贪心切 3（推荐）

核心思路：

当 n <= 3 时，必须剪至少一刀，返回 n - 1。

尽量多切 3，可使乘积最大。

当剩余为 4 时，保留为 2 * 2 更优。

复杂度分析：

时间复杂度：O(1)，常数次运算。

空间复杂度：O(1)，仅使用常数额外空间。

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

        long res = 1;

        // 尽量多切 3
        while (n > 4) {
            res *= 3;
            n -= 3;
        }

        return (int) (res * n);
    }
}

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

	res := int64(1)

	// 尽量多切 3
	for n > 4 {
		res *= 3
		n -= 3
	}

	return int(res * int64(n))
}

相似题目

题目	难度	考察点
343. 整数拆分	中等	贪心/DP
279. 完全平方数	中等	动态规划
650. 只有两个键的键盘	中等	质因数分解
96. 不同的二叉搜索树	中等	动态规划
464. 我能赢吗	中等	记忆化搜索

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/74900259