跳转至

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] 内。

解法

方法一：模拟

思考

对阵按 \(1\) 对 \(n\)、\(2\) 对 \(n-1\) 如此配对，并递归生成下一轮括号串。\(n\) 为 \(2\) 的幂，模拟即可。

用数组存当前轮的队伍（或已生成的对阵串），每一轮把 \(i\) 与 \(n-1-i\) 包成 (a,b) 写回前半，长度减半，直到只剩一项。

我们可以用一个长度为 \(n\) 的数组 \(s\) 来存储每个队伍的编号，然后模拟比赛的过程。

每一轮比赛，我们将数组 \(s\) 中的前 \(n\) 个元素两两配对，然后将胜者的编号存入数组 \(s\) 的前 \(n/2\) 个位置。然后，我们将 \(n\) 减半，继续进行下一轮比赛，直到 \(n\) 减半为 \(1\)，此时数组 \(s\) 中的第一个元素即为最终的比赛匹配方案。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(n \times \log n)\)。其中 \(n\) 为队伍的数量。

1
2
3
4
5
6
7
8
class Solution:
    def findContestMatch(self, n: int) -> str:
        s = [str(i + 1) for i in range(n)]
        while n > 1:
            for i in range(n >> 1):
                s[i] = f"({s[i]},{s[n - i - 1]})"
            n >>= 1
        return s[0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public String findContestMatch(int n) {
        String[] s = new String[n];
        for (int i = 0; i < n; ++i) {
            s[i] = String.valueOf(i + 1);
        }
        for (; n > 1; n >>= 1) {
            for (int i = 0; i < n >> 1; ++i) {
                s[i] = String.format("(%s,%s)", s[i], s[n - i - 1]);
            }
        }
        return s[0];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    string findContestMatch(int n) {
        vector<string> s(n);
        for (int i = 0; i < n; ++i) {
            s[i] = to_string(i + 1);
        }
        for (; n > 1; n >>= 1) {
            for (int i = 0; i < n >> 1; ++i) {
                s[i] = "(" + s[i] + "," + s[n - i - 1] + ")";
            }
        }
        return s[0];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func findContestMatch(n int) string {
    s := make([]string, n)
    for i := 0; i < n; i++ {
        s[i] = strconv.Itoa(i + 1)
    }
    for ; n > 1; n >>= 1 {
        for i := 0; i < n>>1; i++ {
            s[i] = fmt.Sprintf("(%s,%s)", s[i], s[n-i-1])
        }
    }
    return s[0]
}

1
2
3
4
5
6
7
8
9
function findContestMatch(n: number): string {
    const s: string[] = Array.from({ length: n }, (_, i) => (i + 1).toString());
    for (; n > 1; n >>= 1) {
        for (let i = 0; i < n >> 1; ++i) {
            s[i] = `(${s[i]},${s[n - i - 1]})`;
        }
    }
    return s[0];
}

评论