2481.分割圆的最少切割次数

【LetMeFly】2481.分割圆的最少切割次数

力扣题目链接:https://leetcode.cn/problems/minimum-cuts-to-divide-a-circle/

圆内一个 有效切割 ,符合以下二者之一:

  • 该切割是两个端点在圆上的线段,且该线段经过圆心。
  • 该切割是一端在圆心另一端在圆上的线段。

一些有效和无效的切割如下图所示。

给你一个整数 n ,请你返回将圆切割成相等的 n 等分的 最少 切割次数。

 

示例 1:

输入:n = 4
输出:2
解释:
上图展示了切割圆 2 次,得到四等分。

示例 2:

输入:n = 3
输出:3
解释:
最少需要切割 3 次,将圆切成三等分。
少于 3 次切割无法将圆切成大小相等面积相同的 3 等分。
同时可以观察到,第一次切割无法将圆切割开。

 

提示:

  • 1 <= n <= 100

方法一:几何

这道题意思是:最少使用几条直径/半径,能把圆$n$等分。

其实分为两种情况考虑即可:

  • 如果$n$是偶数,我们使用直径分割,每多一条直径,所分成的块数$+2$
  • 如果$n$是奇数,那么无法使用直径分割(否则无法做到等分),每多一条半径,所分成的块数$12$

特别的: 如果要把圆分成1块,那么使用一条半径分割没有意义(因此返回$0$)

  • 时间复杂度$O(1)$
  • 空间复杂度$O(1)$

AC代码

C++

1
2
3
4
5
6
7
8
9
class Solution {
public:
int numberOfCuts(int n) {
if (n == 1) {
return 0;
}
return n % 2 ? n : n / 2;
}
};

Python

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

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/131257304


2481.分割圆的最少切割次数
https://blog.letmefly.xyz/2023/06/17/LeetCode 2481.分割圆的最少切割次数/
作者
Tisfy
发布于
2023年6月17日
许可协议