每日一题:LeetCode:1688.比赛中的配对次数

浏览次数 : 次 2022-01-25

博文字数统计 : 636字 | 阅读所需时长 : 2分

× 文章目录

1. 2022-01-25：LeetCode：1688.比赛中的配对次数

每日一题：LeetCode：1688.比赛中的配对次数
- 时间：2022-01-25
- 力扣难度：Easy
- 个人难度：Easy
- 算法：模拟、数学、递归

2022-01-25：LeetCode：1688.比赛中的配对次数

1. 题目描述

题目：原题链接
- 给你一个整数 n ，表示比赛中的队伍数。比赛遵循一种独特的赛制：
  - 如果当前队伍数是偶数，那么每支队伍都会与另一支队伍配对。总共进行 n / 2 场比赛，且产生 n / 2 支队伍进入下一轮。
  - 如果当前队伍数为奇数，那么将会随机轮空并晋级一支队伍，其余的队伍配对。总共进行 (n - 1) / 2 场比赛，且产生 (n - 1) / 2 + 1 支队伍进入下一轮。
- 返回在比赛中进行的配对次数，直到决出获胜队伍为止。
- 1 <= n <= 200
输入输出规范
- 输入：队伍个数 n
- 输出：比赛次数
输入输出示例
- 输入：n = 14
- 输出：13

2. 方法一：简单模拟

思路
- 根据题目说明的队伍个数在奇偶时的不同情况，分类讨论
- 遍历一次即可

题解：直接模拟

public int numberOfMatches(int n) {
       int count = 0;
       int lucky = n % 2;
       while(n > 1) {
           count += n / 2;
           n = n / 2 + lucky;
       }
       return count;
   }

复杂度分析：n 是输入的队伍个数
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$

3. 方法二：递归

思路
- 同样的，可以将循环遍历写成递归的形式
- 注意递归出口是队伍个数为1

题解

public int numberOfMatches(int n) {
       if(n==1) return 0;
       return n % 2 == 0 ? n/2 + numberOfMatches(n/2) : n/2 + numberOfMatches(n/2 + 1);
   }

复杂度分析：n 是输入的队伍个数
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$

4. 方法三：脑筋急转弯

思路
- 实际上，n 个队伍比赛，不管有没有幸运儿轮空，最后决出冠军时，都只剩下一个队伍
- 换句话说，就是淘汰了 n - 1 个队伍，而不用关系具体过程，除非需要求解比赛的轮数、具体对阵情况
- 因此，淘汰 n - 1 个队伍一定是要进行 n - 1 次比赛，因为本题没有平局，且一场比赛能且只能淘汰一个队伍
- Why：直接返回 n - 1 咋空间才超过 5 %，大佬们！

题解

1
2
3

public int numberOfMatches(int n) {
    return n-1;
}

复杂度分析：n 是输入的队伍个数
- 时间复杂度：$O(1)$
- 空间复杂度：$O(1)$

本文作者： Chthollists
发布时间： 2022-01-25 21:36:45
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:1688.比赛中的配对次数
本文链接： https://chthollists.github.io/post/59ca2bdc.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！