网站排名优化课程,设计素材免费下载网站有哪些,创世网站建设公司,如何给网站2做推广这是一道 简单 题 https://leetcode.cn/problems/minimum-cuts-to-divide-a-circle/ 题目
圆内一个 有效切割 #xff0c;符合以下两个条件之一#xff1a;
该切割是两个端点在圆上的线段#xff0c;且该线段经过圆心#xff0c;即圆的直径。该切割是一端在圆心另一端在圆… 这是一道 简单 题 https://leetcode.cn/problems/minimum-cuts-to-divide-a-circle/ 题目
圆内一个 有效切割 符合以下两个条件之一
该切割是两个端点在圆上的线段且该线段经过圆心即圆的直径。该切割是一端在圆心另一端在圆上的线段即圆的半径。
一些有效和无效的切割如下图所示
第一个和第二个有效分别符合条件一和条件二。第三个无效。
给你一个整数 n n n 请你返回将圆切割成相等的 n n n 等分的 最少 切割次数。
示例 1
输入n 4
输出2
解释 上图展示了切割圆 2 次得到四等分。 示例 2
输入n 3
输出3
解释 最少需要切割 3 次将圆切成三等分。
少于 3 次切割无法将圆切成大小相等面积相同的 3 等分。
同时可以观察到第一次切割无法将圆切割开。 提示
1 n 100 题解
初看这道题的时候其实是有点儿懵的。官方标注的是一道简单题但是看了一眼竟然不知道该如何下手感觉很慌。
理智告诉我要淡定拿出纸和笔先列几个答案出来看看能不能找出规律来。然后哼哧哼哧一顿列还别说真找出规律来了呢顿时松了一口气。 如图所示除了 n 1 n 1 n1 比较特殊不需要分割之外其他的如果 n n n 是偶数那么答案就是分割 n / 2 n/2 n/2 次。如果 n n n 是奇数答案就是分割 n n n 次。
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}
}复杂度分析
时间复杂度 O ( 1 ) O(1) O(1)。 空间复杂度 O ( 1 ) O(1) O(1)。