网络异常,图片无法展示
|
题目描述
这是 LeetCode 上的 1688. 比赛中的配对次数 ,难度为 简单。
Tag : 「模拟」
给你一个整数 n
,表示比赛中的队伍数。比赛遵循一种独特的赛制:
- 如果当前队伍数是 偶数 ,那么每支队伍都会与另一支队伍配对。总共进行
n / 2
场比赛,且产生n / 2
支队伍进入下一轮。 - 如果当前队伍数为 奇数 ,那么将会随机轮空并晋级一支队伍,其余的队伍配对。总共进行
(n - 1) / 2
场比赛,且产生(n - 1) / 2 + 1
支队伍进入下一轮。
返回在比赛中进行的配对次数,直到决出获胜队伍为止。
示例 1:
输入:n = 7 输出:6 解释:比赛详情: - 第 1 轮:队伍数 = 7 ,配对次数 = 3 ,4 支队伍晋级。 - 第 2 轮:队伍数 = 4 ,配对次数 = 2 ,2 支队伍晋级。 - 第 3 轮:队伍数 = 2 ,配对次数 = 1 ,决出 1 支获胜队伍。 总配对次数 = 3 + 2 + 1 = 6 复制代码
示例 2:
输入:n = 14 输出:13 解释:比赛详情: - 第 1 轮:队伍数 = 14 ,配对次数 = 7 ,7 支队伍晋级。 - 第 2 轮:队伍数 = 7 ,配对次数 = 3 ,4 支队伍晋级。 - 第 3 轮:队伍数 = 4 ,配对次数 = 2 ,2 支队伍晋级。 - 第 4 轮:队伍数 = 2 ,配对次数 = 1 ,决出 1 支获胜队伍。 总配对次数 = 7 + 3 + 2 + 1 = 13 复制代码
提示:
- 1 <= n <= 200
脑筋急转弯
这个题不能浪费了,吃个鱼啥的吧 🤣
共有 nn 支队伍,每场比赛淘汰一支,最终剩下一支冠军队,即有 n - 1n−1 支队伍需要通过 n - 1n−1 场比赛来被淘汰。
代码(感谢 @5cm/s 🌸 烟花总提供的所有语言版本 🤣 🤣 ):
class Solution { public int numberOfMatches(int n) { return n - 1; } } 复制代码
class Solution { public: int numberOfMatches(int n) { return n - 1; } }; 复制代码
class Solution(object): def numberOfMatches(self, n): return n - 1 复制代码
class Solution: def numberOfMatches(self, n: int) -> int: return n - 1 复制代码
int numberOfMatches(int n){ return n - 1; } 复制代码
public class Solution { public int NumberOfMatches(int n) { return n - 1; } } 复制代码
var numberOfMatches = function(n) { return n - 1 }; 复制代码
function numberOfMatches(n: number): number { return n - 1 }; 复制代码
def number_of_matches(n) n - 1 end 复制代码
class Solution { func numberOfMatches(_ n: Int) -> Int { return n - 1 } } 复制代码
func numberOfMatches(n int) int { return n - 1 } 复制代码
object Solution { def numberOfMatches(n: Int): Int = { return n - 1 } } 复制代码
class Solution { fun numberOfMatches(n: Int): Int { return n - 1 } } 复制代码
impl Solution { pub fn number_of_matches(n: i32) -> i32 { n - 1 } } 复制代码
class Solution { function numberOfMatches($n) { return $n - 1; } } 复制代码
(define/contract (number-of-matches n) (-> exact-integer? exact-integer?) (- n 1) ) 复制代码
-spec number_of_matches(N :: integer()) -> integer(). number_of_matches(N) -> N - 1. 复制代码
defmodule Solution do @spec number_of_matches(n :: integer) :: integer def number_of_matches(n) do n - 1 end end 复制代码
- 时间复杂度:O(1)O(1)
- 空间复杂度:O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1688
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour… 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。