【算法题解】52. 分割圆的最少切割次数

❝

这是一道 「简单」 题
https://leetcode.cn/problems/minimum-cuts-to-divide-a-circle/

❞

题目

圆内一个 有效切割 ，符合以下两个条件之一：

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

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

第一个和第二个有效，分别符合条件一和条件二。第三个无效。

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

示例 1：

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

示例 2：

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

提示：

1 <= n <= 100

题解

初看这道题的时候其实是有点儿懵的。官方标注的是一道简单题，但是看了一眼竟然不知道该如何下手，感觉很慌。

理智告诉我要淡定，拿出纸和笔，先列几个答案出来看看能不能找出规律来。然后哼哧哼哧一顿列，还别说，真找出规律来了呢，顿时松了一口气。

如图所示：除了比较特殊不需要分割之外，其他的如果是偶数，那么答案就是分割次。如果是奇数，答案就是分割次。

Java 代码实现

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

Go 代码实现

func numberOfCuts(n int) int {
    if n == 1 {
        return 0
    }

    if n % 2 == 0 {
        return n / 2
    }else {
        return n
    }
}

复杂度分析

时间复杂度：。
空间复杂度：。

马后炮一下

其实可以想到的，如果是按照圆的直径来分割，那么肯定被分成偶数块。如条直径分成块，条直径分成块，条直径分成块，条直径分成块。所以被分出的块数是偶数的时候，需要条直径即可。

如果是奇数，所有参与分割的必须都是半径，且任意两条半径分割线都不能在一条直线上，否则就可以连成一条直径了。这个结论用反证法，假设有一条直径，那么这条直径肯定会将圆分成相等的两份，那么在这相同的两份半圆的基础上来分出相同大小的奇数块是不可能完成的任务，因为只有两个半圆分别分割出的块数不等的情况下加起来才能是奇数，而一模一样的两个半圆分出的块数不等的话，其大小肯定也就不一样了。所以都是半径的话，分成几块就需要几条半径来分割。

– End –