返回介绍

solution / 2400-2499 / 2481.Minimum Cuts to Divide a Circle / README

发布于 2024-06-17 01:03:05 字数 2999 浏览 0 评论 0 收藏 0

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}$ 次切割。

综上,可以得到:

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

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

class Solution:
  def numberOfCuts(self, n: int) -> int:
    return n if (n > 1 and n & 1) else n >> 1
class Solution {
  public int numberOfCuts(int n) {
    return n > 1 && n % 2 == 1 ? n : n >> 1;
  }
}
class Solution {
public:
  int numberOfCuts(int n) {
    return n > 1 && n % 2 == 1 ? n : n >> 1;
  }
};
func numberOfCuts(n int) int {
  if n > 1 && n%2 == 1 {
    return n
  }
  return n >> 1
}
function numberOfCuts(n: number): number {
  return n > 1 && n & 1 ? n : n >> 1;
}
impl Solution {
  pub fn number_of_cuts(n: i32) -> i32 {
    if n > 1 && n % 2 == 1 {
      return n;
    }
    n >> 1
  }
}
public class Solution {
  public int NumberOfCuts(int n) {
    return n > 1 && n % 2 == 1 ? n : n >> 1;
  }
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文