前言

• 大家好，我是新人简书博主：「 个人主页」主要分享程序员生活、编程技术、* * 以及每日的LeetCode刷题记录，欢迎大家关注我，一起学习交流，谢谢！
• 正在坚持每日更新LeetCode每日一题，发布的题解有些会参考其他大佬的思路(参考资料的链接会放在最下面)，欢迎大家关注我 ~ ~ ~
• 同时也在进行其他专项类型题目的刷题与题解活动，相关资料也会同步到「GitHub」上面 ~
• 今天是坚持写题解的29天(haha，从21年圣诞节开始的)，大家一起加油

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

Chtholly.jpg

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 是输入的队伍个数

  • 时间复杂度：
  • 空间复杂度：

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 是输入的队伍个数

  • 时间复杂度：
  • 空间复杂度：

4. 方法三：脑筋急转弯

• 思路

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

• 题解

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

• 复杂度分析：n 是输入的队伍个数

  • 时间复杂度：
  • 空间复杂度：

最后

如果本文有所帮助的话，欢迎大家可以给个三连「点赞」&「收藏」&「关注」 ~ ~ ~
也希望大家有空的时候光临我的其他平台，上面会更新Java面经、八股文、刷题记录等等，欢迎大家光临交流，谢谢！

• 「个人博客」
• 「掘金」
• 「LeetCode」