544. 输出比赛匹配对 🔒
题目描述
在 NBA 季后赛期间,我们总是安排相对强大的球队与相对弱小的球队比赛,就像让排名第 1
的球队与排名第 n
的球队比赛一样,这是一种使比赛更加有趣的好策略。
现给定 n
支球队,请以字符串的形式返回它们的最终的比赛匹配方案。
这 n
支球队从 1
到 n
进行标记,代表它们的初始排名(即,排名 1
的是最强的球队,排名 n
的是最弱的球队)。
我们将使用括号 '('
和 ')'
以及逗号 ','
来表示比赛的匹配情况。我们使用括号来表示匹配,逗号来表示分组。在每一轮的匹配过程中,你总是需要遵循使相对强大的球队与相对弱小的球队配对的策略。
示例 1:
输入: n = 4 输出: "((1,4),(2,3))" 解释: 在第一轮,我们将队伍 1 和 4 配对,2 和 3 配对,以满足将强队和弱队搭配的效果。得到(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)))。
提示:
n == 2x
,并且x
在范围[1,12]
内。
解法
方法一:模拟
假设 team[i]
为当前轮次中第 i 强的队伍。
每一轮,将第 i 支队伍变成 "(" + team[i] + "," + team[n-1-i] + ")"
,并且每一轮淘汰一半的队伍。
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|