README.md

comments	difficulty	edit_url	rating	source	tags
true	简单	https://github.com/doocs/leetcode/edit/main/solution/2400-2499/2481.Minimum%20Cuts%20to%20Divide%20a%20Circle/README.md	1246	第 92 场双周赛 Q1	几何 数学

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

English Version

题目描述

圆内一个 有效切割 ，符合以下二者之一：

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

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

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

 

示例 1：

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

示例 2：

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

 

提示：

• 1 <= n <= 100

解法

方法一：分类讨论

• 当 $n=1$ 时，不需要切割，即切割次数为 $0$；
• 当 $n$ 为奇数时，不存在共线的情况，最少需要 $n$ 次切割；
• 当 $n$ 为偶数时，可以两两共线，最少需要 $\frac{n}{2}$ 次切割。

综上，可以得到：

$$ \textit{ans} = \begin{cases} n, & n \gt 1 \textit{ 且 } n \textit{ 为奇数} \\ \frac{n}{2}, & n \textit{ 为其它} \\ \end{cases} $$

时间复杂度 $O(1)$，空间复杂度 $O(1)$。

Python3

class Solution:
    def numberOfCuts(self, n: int) -> int:
        return n if (n > 1 and n & 1) else n >> 1

Java

class Solution {
    public int numberOfCuts(int n) {
        return n > 1 && n % 2 == 1 ? n : n >> 1;
    }
}

C++

class Solution {
public:
    int numberOfCuts(int n) {
        return n > 1 && n % 2 == 1 ? n : n >> 1;
    }
};

Go

func numberOfCuts(n int) int {
	if n > 1 && n%2 == 1 {
		return n
	}
	return n >> 1
}

TypeScript

function numberOfCuts(n: number): number {
    return n > 1 && n & 1 ? n : n >> 1;
}

Rust

impl Solution {
    pub fn number_of_cuts(n: i32) -> i32 {
        if n > 1 && n % 2 == 1 {
            return n;
        }
        n >> 1
    }
}

C#

public class Solution {
    public int NumberOfCuts(int n) {
        return n > 1 && n % 2 == 1 ? n : n >> 1;
    }
}