比赛中的配对次数

难度: Easy

给你一个整数 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

Submission

运行时间: 24 ms

内存: 0.0 MB

class Solution:
    def numberOfMatches(self, n: int) -> int:
        res = 0
        while n>1:
            if n%2==0:
                n = n//2
                res+=n
            else:
                n = n//2
                res+=n
                n+=1
            
        return res

Explain

该题解采用模拟赛程的方式来计算总配对次数。对于给定的队伍数n，如果n是偶数，则直接将n除以2得到本轮比赛的配对次数和晋级的队伍数；如果n是奇数，则先将n减1后除以2计算配对次数，然后使晋级的队伍数为(n-1)/2 + 1。循环继续，直到只剩下一个队伍（n=1），即决出获胜队伍。每轮比赛结束后，将本轮的配对次数累加到结果中。通过这种方式，可以模拟整个比赛的过程，得到总的配对次数。

时间复杂度: O(log n)

空间复杂度: O(1)

class Solution:
    def numberOfMatches(self, n: int) -> int:
        res = 0  # 初始化总配对次数为0
        while n > 1:  # 当队伍数大于1时继续比赛
            if n % 2 == 0:
                n = n // 2  # n是偶数时，直接减半
                res += n  # 加上本轮配对次数
            else:
                n = n // 2  # n是奇数时，先减半计算配对次数
                res += n  # 加上本轮配对次数
                n += 1  # 晋级队伍数为(n-1)/2 + 1
        return res  # 返回总配对次数

Explore

在队伍数为奇数时，晋级队伍数要加1是为了保证有一个队伍直接晋级到下一轮，从而保持比赛的进行。因为奇数队伍无法完全配对，总会剩下一个无法配对的队伍，这个队伍自动晋级以保持比赛的连续性。这种处理实际上不会导致比赛轮次增加，因为每一轮比赛的队伍数量总是朝向减少至1的方向进行，即使队伍数为奇数时晋级数稍增，但总体上比赛轮次是由初始队伍数决定的，这与队伍数每轮减半的趋势相符。

题解中提到的每轮比赛队伍数量大致减半是一种近似表述。对于偶数个队伍，这是准确的；对于奇数个队伍，实际晋级的队伍数会比减半稍多一个，因此队伍数量减少的速度略慢于严格的一半。如果队伍数从奇数变为偶数，这主要影响的是下一轮的配对方式，但对总轮次的计算影响不大，因为每轮的减少趋势仍然是接近一半，从而确保比赛在对数时间内完成。

Python中的整数除法（使用 // 运算符）进行的是向下取整除法。这意味着对于正整数来说，// 运算符总是返回最接近零的结果，这在大多数情况下与其他语言的标准整数除法行为一致。在这个特定算法中，使用 // 运算符是为了确保即使在队伍数为奇数时，也能正确计算出需要配对的队伍数和剩余的单一队伍。因此，这种处理方式不会影响算法结果的正确性。

在实际的比赛场景中，队伍数n应该是一个正整数。因此，从理论和实用的角度看，输入n为非正整数是没有实际意义的。如果要使算法更健壮，可以在算法开始时添加输入验证，确保n是一个正整数。如果输入n<=0，可以直接返回0，表示没有有效的比赛或配对发生，或者抛出一个错误提示输入不合法。