Skip to content

Latest commit

 

History

History
146 lines (110 loc) · 4.08 KB

File metadata and controls

146 lines (110 loc) · 4.08 KB

English Version

题目描述

在 NBA 季后赛中,我们总是安排较强的队伍对战较弱的队伍,例如用排名第 1 的队伍和第 n 的队伍对决,这是一个可以让比赛更加有趣的好策略。现在,给你 支队伍,你需要以字符串格式输出它们的 最终 比赛配对。

n 支队伍按从 1 到 n 的正整数格式给出,分别代表它们的初始排名(排名 1 最强,排名 n 最弱)。我们用括号('(', ')')和逗号(',')来表示匹配对——括号('(', ')')表示匹配,逗号(',')来用于分割。 在每一轮的匹配过程中,你都需要遵循将强队与弱队配对的原则。

 

示例 1:

输入: 2
输出: (1,2)
解析: 
初始地,我们有队1和队2两支队伍,按照1,2排列。
因此 用 '(', ')' 和 ','来将队1和队2进行配对,得到最终答案。

示例 2:

输入: 4
输出: ((1,4),(2,3))
解析: 
在第一轮,我们将队伍1和4配对,2和3配对,以满足将强队和弱队搭配的效果。得到(1,4),(2,3).
在第二轮,(1,4) 和 (2,3) 的赢家需要进行比赛以确定最终赢家,因此需要再在外面加一层括号。
于是最终答案是((1,4),(2,3))。

示例 3:

输入: 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)))。

 

注意:

  1. 的范围是 [2, 212].
  2. 保证 n 可以写成 2k 的形式,其中 k 是正整数。

 

解法

方法一:模拟

假设 team[i] 为当前轮次中第 i 强的队伍。

每一轮,将第 i 支队伍变成 "(" + team[i] + "," + team[n-1-i] + ")",并且每一轮淘汰一半的队伍。

Python3

class Solution:
    def findContestMatch(self, n: int) -> str:
        team = [str(i + 1) for i in range(n)]
        while n > 1:
            for i in range(n >> 1):
                team[i] = f'({team[i]},{team[n - 1 - i]})'
            n >>= 1
        return team[0]

Java

class Solution {
    public String findContestMatch(int n) {
        String[] team = new String[n];
        for (int i = 0; i < n; ++i) {
            team[i] = "" + (i + 1);
        }
        for (; n > 1; n /= 2) {
            for (int i = 0; i < n / 2; ++i) {
                team[i] = "(" + team[i] + "," + team[n - 1 - i] + ")";
            }
        }
        return team[0];
    }
}

C++

class Solution {
public:
    string findContestMatch(int n) {
        vector<string> team(n);
        for (int i = 0; i < n; ++i) team[i] = to_string(i + 1);
        for (; n > 1; n >>= 1) {
            for (int i = 0; i<n> > 1; ++i) {
                team[i] = "(" + team[i] + "," + team[n - 1 - i] + ")";
            }
        }
        return team[0];
    }
};

Go

func findContestMatch(n int) string {
	team := make([]string, n)
	for i := range team {
		team[i] = strconv.Itoa(i + 1)
	}
	for n > 1 {
		for i := 0; i < n>>1; i++ {
			team[i] = "(" + team[i] + "," + team[n-1-i] + ")"
		}
		n >>= 1
	}
	return team[0]
}

...