---

0544. 输出比赛匹配对

• 标签：递归、字符串、模拟
• 难度：中等

题目链接

• 0544. 输出比赛匹配对 - 力扣

题目大意

描述：

给定一个整数 $n$，表示有 $n$ 支队伍参加 NBA 季后赛比赛，编号从 $1$ 到 $n$。

比赛规则：

• 第一轮：编号最小的队伍与编号最大的队伍配对，第二小的与第二大的配对，以此类推。
• 每轮比赛后，获胜队伍进入下一轮。
• 重复上述过程，直到决出冠军。

要求：

输出表示比赛配对的字符串。

使用括号 '(' 和 ')' 以及逗号 ',' 来表示比赛的匹配情况。其中括号用来表示匹配，逗号用来表示分组。

说明：

• $n == 2^x$，并且 $x$ 在范围 $[1, 12]$ 内。

示例：

• 示例 1：

输入：n = 4
输出："((1,4),(2,3))"
解释：
第一轮：队伍 1 和 4 配对，队伍 2 和 3 配对。
第二轮：(1,4) 的获胜者和 (2,3) 的获胜者配对。

• 示例 2：

输入：n = 8
输出："(((1,8),(4,5)),((2,7),(3,6)))"
解释：
第一轮：(1,8),(2,7),(3,6),(4,5)
第二轮：((1,8),(4,5)),((2,7),(3,6))
第三轮：(((1,8),(4,5)),((2,7),(3,6)))
由于第三轮会决出最终胜者，故输出答案为(((1,8),(4,5)),((2,7),(3,6)))

解题思路

思路 1：模拟 + 递归

使用列表存储每轮的配对结果，初始时每个队伍是一个字符串。

每轮比赛：

1. 将队伍列表首尾配对：$teams[i]$ 和 $teams[n-1-i]$ 配对
2. 配对结果为 $(teams[i], teams[n-1-i])$
3. 将配对结果作为新的队伍列表
4. 重复直到只剩一个元素

思路 1：代码

class Solution:
    def findContestMatch(self, n: int) -> str:
        # 初始化队伍列表
        teams = [str(i) for i in range(1, n + 1)]
        
        # 模拟每轮比赛
        while len(teams) > 1:
            next_round = []
            # 首尾配对
            for i in range(len(teams) // 2):
                match = f"({teams[i]},{teams[len(teams) - 1 - i]})"
                next_round.append(match)
            teams = next_round
        
        return teams[0]

思路 1：复杂度分析

• 时间复杂度：$O(n \log n)$，共有 $\log n$ 轮比赛，每轮需要处理 $O(n)$ 个队伍（字符串拼接）。
• 空间复杂度：$O(n)$，需要存储每轮的配对结果。