企业官网建设流程全解析

• 教程
• 文档
• 知识库

导读

本篇题解来自 AlgoNote（算法通关手册）0500-0599 题解集合，围绕 LeetCode 0544「输出比赛匹配对」展开。该题要求以括号与逗号构造的字符串形式，完整输出 NBA 季后赛式淘汰赛中从第一轮到决出冠军的每一轮配对结构。读完本文，你将掌握一种「自底向上逐轮模拟、同时用字符串累积括号嵌套」的迭代构造方法，理解它为何天然对应递归/分治思想，并能举一反三地处理同类"过程式结果输出"问题。

题目背景与核心规则

给定整数 $n$，表示有 $n$ 支队伍参加季后赛，编号从 $1$ 到 $n$。比赛遵循以下规则：

• 第一轮配对：编号最小的队伍与编号最大的队伍配对，第二小的与第二大的配对，以此类推，即按"首尾相向"方式两两配对；
• 逐轮晋级：每轮比赛结束后，获胜队伍进入下一轮，下一轮继续沿用同一配对规则；
• 决出冠军：重复上述过程，直到只剩下一支队伍。

输出要求使用括号'('、')'与逗号','表达完整比赛配对情况：括号表示一场匹配，逗号表示分组。约束条件为 $n == 2^x$，且 $x$ 在 $[1, 12]$ 范围内，即队伍数量必为 2 的幂，保证每轮都能完全两两配对、最终恰好决出冠军。

示例推演：从输入到输出

示例 1：$n = 4$

输入：n = 4 输出："((1,4),(2,3))"

推演过程：

• 第一轮：队伍 1 与 4 配对、队伍 2 与 3 配对；
• 第二轮：第一轮两个配对的获胜者再配对，即(1,4)的胜者对(2,3)的胜者。

由于第二轮已决出冠军，输出为((1,4),(2,3))。

示例 2：$n = 8$

输入：n = 8 输出："(((1,8),(4,5)),((2,7),(3,6)))"

推演过程（共三轮）：

1. 第一轮：(1,8)、(2,7)、(3,6)、(4,5)；
2. 第二轮：((1,8),(4,5))、((2,7),(3,6))；
3. 第三轮：(((1,8),(4,5)),((2,7),(3,6)))，决出最终胜者。

最终答案即第三轮的完整嵌套字符串。可以看到，输出字符串的括号层数恰好等于比赛轮数，且最内层的括号是第一轮的配对，越往外越接近决赛——这正是"自底向上累积字符串"这一做法的直观体现。

解题思路：模拟 + 递归（迭代版）

算法设计

题解采用"每轮模拟 + 字符串累积"的策略，核心想法是：

1. 初始化队伍列表：用列表存储当前轮次的全部队伍，初始时每支队伍就是其编号字符串"1"、"2"、……、"n"；
2. 逐轮首尾配对：对当前列表，将teams[i]与teams[len(teams) - 1 - i]配对，生成字符串(teams[i],teams[len(teams)-1-i])，存入下一轮列表；
3. 列表替换：将配对结果列表作为新一轮队伍列表；
4. 终止条件：重复直到列表只剩一个元素，该元素即为最终答案。

完整代码

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]

代码细节解读

• 初始化：[str(i) for i in range(1, n + 1)]生成 $n$ 个编号字符串，对应第一轮前的 $n$ 支队伍；
• 轮次循环：while len(teams) > 1保证循环次数恰为 $\log_2 n$（从 $n$ 支队伍逐轮减半到 1）；
• 首尾配对：循环范围取len(teams) // 2，一次处理一对队伍；teams[i]与teams[len(teams) - 1 - i]恰好满足"最小配最大、次小配次大"的规则；
• 字符串累积：每次配对用 f-string 生成(a,b)形式的新字符串，下一轮直接将其视为"一支新队伍"参与配对，从而天然累积出多层的括号嵌套。

以 $n = 8$ 手动跟踪：

• 初始teams = ["1","2","3","4","5","6","7","8"]；
• 第 1 轮后：["(1,8)","(2,7)","(3,6)","(4,5)"]；
• 第 2 轮后：["((1,8),(4,5))","((2,7),(3,6))"]；
• 第 3 轮后：["(((1,8),(4,5)),((2,7),(3,6)))"]，长度 1，循环结束。

复杂度分析

• 时间复杂度：$O(n \log n)$。共有 $\log_2 n$ 轮比赛（即 $\log_2 n$ 次循环），每轮需要遍历当前列表中的全部 $O(n)$ 支队伍并完成字符串拼接，故总复杂度为 $O(n \log n)$。
• 空间复杂度：$O(n)$。每轮需要新建一个next_round列表存储配对结果，列表总规模与队伍数量同阶，同时拼接出的字符串总长度也随轮次累积，整体空间占用为 $O(n)$。

算法思想纵深：为何是"递归 / 分治"结构

题目标签为「递归、字符串、模拟」，这并非巧合，从算法结构上可以拆解出三层关系：

1. 模拟层：代码按轮次一步步推进，把"比赛流程"忠实翻译成循环操作，属于典型的过程模拟。仓库中大量题解同样采用模拟思路，例如 螺旋矩阵 II、Z 字形变换 等，都是"按题意逐步构造结果"的同类范式。

2. 递归 / 分治层：观察输出字符串的结构可以发现，$n$ 支队伍的最终配对串可以看作两个规模为 $n/2$ 的子配对串合并的结果——即(左半区的决赛串, 右半区的决赛串)。这完全符合 分治算法 的"分解 → 求解 → 合并"三步结构，也符合 递归算法 中"向下递推、向上回归"的描述：每一层的配对规则相同，只是规模减半。本题的迭代写法本质上是自底向上地完成了这个递归过程：最内层括号（第一轮配对）最先构造，随后逐层"合并"成更大规模的配对串。

3. 双指针层：每轮配对的"首尾相向"移动方式，正是 数组双指针 中的对撞指针模式——左指针从头部向右、右指针从尾部向左，直到两者相遇。若去掉外层轮次循环，仅看单轮配对，代码与对撞指针模板高度一致。

理解了这三层关系，就可以灵活改写：例如用真正的递归函数solve(teams)在规模为 1 时返回队伍串、否则返回(solve(左半), solve(右半))的合并结果，同样能得到正确答案；也可以在不拼接字符串的情况下先求出每轮配对的对子顺序，再统一构造括号串。

边界与输入约束讨论

• 为什么 $n$ 必须是 2 的幂：只有队伍数为 2 的幂，每轮才能恰好两两配对，且最终恰好决出一支冠军；题解中的while len(teams) > 1循环依赖这一性质保证每次都能整除配对。
• $x$ 范围 $[1, 12]$：即 $n$ 最大为 $2^{12} = 4096$。该约束保证输出字符串长度在合理范围内，也意味着最坏情况下循环仅 12 轮，字符串拼接的总开销完全可控。
• 空输入与单队情况：题目保证 $x \ge 1$，即 $n \ge 2$，不会出现单支队伍无需比赛的退化情形；若出现，题解逻辑也会正确返回teams[0]。

小结与延伸

「输出比赛匹配对」是一道典型的过程模拟 + 递归结构题目，解题核心在于把握两点：

• 配对规则固定：每轮都按"首尾相向"配对，可用对撞指针模式在 $O(n)$ 内完成一轮；
• 结果逐层累积：把配对串当作新队伍继续参与配对，即可自底向上构造出多层括号嵌套的最终字符串，时间总代价 $O(n \log n)$。

掌握本题后，建议进一步练习同类"按流程构造输出"的模拟题（如 螺旋矩阵、Z 字形转换），并结合 递归算法、分治算法、双指针 三个基础章节理解其底层思想来源。完整题解列表可参阅 0500-0599 题解索引 与 题解总表。

• 教程
• 文档
• 知识库