在 NBA 季后赛中,我们总是安排较强的队伍对战较弱的队伍,例如用排名第 1 的队伍和第 n 的队伍对决,这是一个可以让比赛更加有趣的好策略。现在,给你 n 支队伍,你需要以字符串格式输出它们的 最终 比赛配对。
n 支队伍按从 1 到 n 的正整数格式给出,分别代表它们的初始排名(排名 1 最强,排名 n 最弱)。我们用括号('(', ')')和逗号(',')来表示匹配对——括号('(', ')')表示匹配,逗号(',')来用于分割。 在每一轮的匹配过程中,你都需要遵循将强队与弱队配对的原则。
Example 1:
Input: 2
Output: (1,2)
Explanation:
初始地,我们有队1和队2两支队伍,按照1,2排列。
因此 用 '(', ')' 和 ','来将队1和队2进行配对,得到最终答案。
Example 2:
Input: 4
Output: ((1,4),(2,3))
Explanation:
在第一轮,我们将队伍1和4配对,2和3配对,以满足将强队和弱队搭配的效果。得到(1,4),(2,3).
在第二轮,(1,4) 和 (2,3) 的赢家需要进行比赛以确定最终赢家,因此需要再在外面加一层括号。
于是最终答案是((1,4),(2,3))。
Example 3:
Input: 8
Output: (((1,8),(4,5)),((2,7),(3,6)))
Explanation:
第一轮: (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)))。
Note: The n is in range [2, 212]. We ensure that the input n can be converted into the form 2k, where k is a positive integer.
题目大意:n个队比赛,排位分别为1~n,安排第1和第n比,第2和第n-1比,如此类推,用括号表示(1,n).比完第一轮,胜者进入下一轮,用双重括号表示:((y,n-y), (x, n-x))直到比出最后冠军.输出比赛安排.
解题思路:很简单,每一轮都是第i和第n-i比,然后进行logn轮
class Solution {
public:
string findContestMatch(int n) {
vector<string> res(n);
for (int i = 0; i < n; i++) { //先将1~n转成字符存入res
res[i] = to_string(i+1);
}
while (n/2) { //从n到1,共进行logn轮
for (int i = 0; i < n/2; i++) { //每轮n/2对
res[i] = "(" + res[i] + "," + res[n-1-i] + ")"; //i与n-1-i比
}
n /= 2; //n折半
}
return res[0]; //最后返回0号位
}
};