class Solution {
public:
string findContestMatch(int n) {
}
};
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] 内。原站题解
rust 解法, 执行用时: 4 ms, 内存消耗: 2.4 MB, 提交时间: 2023-10-17 14:38:00
impl Solution {
pub fn find_contest_match(n: i32) -> String {
let mut ans = (1..=n).map(|x| x.to_string()).collect::<Vec<_>>();
let mut i = n;
while i > 1 {
let mut tmp = vec![];
let n = ans.len();
for j in 0..n/2 {
tmp.push(format!("({},{})", ans[j], ans[n-j-1]));
}
ans = tmp;
i /= 2;
}
ans[0].clone()
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 3.4 MB, 提交时间: 2023-10-17 14:37:16
func findContestMatch1(n int) string {
dq := []string{}
for i := 1; i <= n; i++ {
dq = append(dq, strconv.Itoa(i))
}
for len(dq) > 1 {
nxtdq := []string{}
for len(dq) > 0 {
firt := dq[0]
second := dq[len(dq)-1]
nxtdq = append(nxtdq, "("+firt+","+second+")")
dq = dq[1:len(dq)-1]
}
dq = nxtdq
}
return dq[0]
}
func findContestMatch2(n int) string {
res := []string{}
for i := 1; i <= n; i++ {
res = append(res, strconv.Itoa(i))
}
for n > 1 {
for i := 0; i < n; i++ {
res[i] = "("+res[i]+","+res[n-i-1]+")"
}
n /= 2
}
return res[0]
}
// 模拟即可
func findContestMatch(n int) string {
ss := make([]string, n)
for i := 1; i <= n; i++ {
ss[i-1] = strconv.Itoa(i)
}
for n > 1 {
for i := 0; i < n>>1; i++ {
ss[i] = fmt.Sprintf("(%s,%s)", ss[i], ss[n-i-1])
}
n >>= 1
}
return ss[0]
}
java 解法, 执行用时: 1 ms, 内存消耗: 39.5 MB, 提交时间: 2023-10-17 14:34:19
class Solution {
int[] team;
int t;
StringBuilder ans;
public String findContestMatch(int n) {
team = new int[n];
t = 0;
ans = new StringBuilder();
write(n, Integer.numberOfTrailingZeros(n));
return ans.toString();
}
public void write(int n, int round) {
if (round == 0) {
int w = Integer.lowestOneBit(t);
team[t] = w > 0 ? n / w + 1 - team[t - w] : 1;
ans.append("" + team[t++]);
} else {
ans.append("(");
write(n, round - 1);
ans.append(",");
write(n, round - 1);
ans.append(")");
}
}
}
java 解法, 执行用时: 9 ms, 内存消耗: 41 MB, 提交时间: 2023-10-17 14:32:37
class Solution {
public String findContestMatch(int n) {
String[] team = new String[n];
for (int i = 1; i <= n; ++i)
team[i-1] = "" + i;
for (; n > 1; n /= 2)
for (int i = 0; i < n / 2; ++i)
team[i] = "(" + team[i] + "," + team[n-1-i] + ")";
return team[0];
}
}
python3 解法, 执行用时: 40 ms, 内存消耗: 17 MB, 提交时间: 2023-10-17 14:31:12
class Solution:
# 模拟
def findContestMatch1(self, n: int) -> str:
# team[i] 当前轮第i强
team = [f'{i}' for i in range(1, n+1)]
while n > 1:
for i in range(n//2):
team[i] = f'({team[i]},{team.pop()})'
n /= 2
return team[0]
# 线性输出
def findContestMatch(self, n: int) -> str:
team = []
ans = []
def write(r: int):
if r == 0:
i = len(team)
w = i & -i
team.append(n//w+1 - team[i-w] if w else 1)
ans.append(str(team[-1]))
else:
ans.append("(")
write(r-1)
ans.append(",")
write(r-1)
ans.append(")")
write(int(math.log(n, 2)))
return ''.join(ans)