分割圆的最少切割次数

A valid cut in a circle can be:

• A cut that is represented by a straight line that touches two points on the edge of the circle and passes through its center, or
• A cut that is represented by a straight line that touches one point on the edge of the circle and its center.

Some valid and invalid cuts are shown in the figures below.

Given the integer n, return the minimum number of cuts needed to divide a circle into n equal slices.

 

Example 1:

Input: n = 4
Output: 2
Explanation: 
The above figure shows how cutting the circle twice through the middle divides it into 4 equal slices.

Example 2:

Input: n = 3
Output: 3
Explanation:
At least 3 cuts are needed to divide the circle into 3 equal slices. 
It can be shown that less than 3 cuts cannot result in 3 slices of equal size and shape.
Also note that the first cut will not divide the circle into distinct parts.

 

Constraints:

• 1 <= n <= 100

// 思路：
// 同样的逻辑可以用 Java Stream 来实现，但在这种简单的情况下，使用 Stream 并不是最合适的。
// 这里只是为了展示如何使用 Stream 进行简单的整数计算。

import java.util.stream.IntStream;

public class Solution {
    public int minCuts(int n) {
        // 使用 IntStream.range 生成一个范围，然后使用 map 进行判断
        return IntStream.range(0, n)
                         .map(i -> (n % 2 == 0) ? n / 2 : n)
                         .findFirst()
                         .getAsInt();
    }
}

题解的核心思路是基于圆的切割方式和需要的等分数。这里有两种主要的切割方式：经过圆心的直径切割和单侧经过圆心的半径切割。当需要将圆切割成偶数等分时，可以通过一半数量的直径切割来完成，因为每个直径切割将圆切成两部分。如果是奇数等分，则每部分必须单独进行切割，因此需要的切割次数等于等分数 n。根据题目条件，我们可以得出对于 n = 1 不需要切割，对于偶数最少需要 n/2 次切割，对于奇数则是 n 次。

O(1)

O(1)