Easy

题目描述

圆的有效切割可以是：

  • 一条通过圆心并且触及圆边缘两点的直线切割，或
  • 一条通过圆心并且触及圆边缘一点的直线切割。

下面的图展示了一些有效和无效的切割。

给定整数 n，返回将圆分割为 n 个相等扇形所需的最少切割次数。

示例 1：

输入：n = 4
输出：2
解释：
上图显示了通过圆心切割两次如何将圆分为 4 个相等的扇形。

示例 2：

输入：n = 3
输出：3
解释：
至少需要 3 次切割才能将圆分为 3 个相等的扇形。
可以证明少于 3 次切割无法产生 3 个大小和形状相等的扇形。
还要注意第一次切割不会将圆分成不同的部分。

约束：

  • 1 <= n <= 100

提示：

  • 分别考虑奇数和偶数值。
  • 什么时候我们完全不需要切割圆？

解题思路

这道题需要分析圆的切割规律。关键在于理解不同情况下的切割需求：

  1. 特殊情况 n = 1：如果只需要 1 个扇形，那么整个圆就是一个扇形，无需切割，返回 0。

  2. 偶数情况：当 n 为偶数时，我们可以利用通过圆心的直径切割。每条直径可以将圆分成 2 部分，所以需要 n/2 次切割就能得到 n 个相等扇形。

  3. 奇数情况：当 n 为奇数且 n > 1 时，无法仅用直径切割来平均分割。我们需要从圆心到边缘的半径切割，每次切割增加一个扇形，所以需要 n 次切割。

解题思路总结：

  • 如果 n = 1，返回 0（无需切割）
  • 如果 n 为偶数，返回 n/2（用直径切割）
  • 如果 n 为奇数且 n > 1，返回 n（用半径切割）

这个规律可以简化为：当 n = 1 时返回 0，当 n 为偶数时返回 n/2，否则返回 n。

代码实现

class Solution {
public:
    int numberOfCuts(int n) {
        if (n == 1) {
            return 0;
        }
        return (n % 2 == 0) ? n / 2 : n;
    }
};

class Solution:
    def numberOfCuts(self, n: int) -> int:
        if n == 1:
            return 0
        return n // 2 if n % 2 == 0 else n

public class Solution {
    public int NumberOfCuts(int n) {
        if (n == 1) {
            return 0;
        }
        return (n % 2 == 0) ? n / 2 : n;
    }
}

var numberOfCuts = function(n) {
    if (n === 1) return 0;
    return n % 2 === 0 ? n / 2 : n;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(1) - 只需要常数时间的数学计算
空间复杂度O(1) - 只使用常数额外空间

相关题目