OutputContestMatches [source code]

public class OutputContestMatches {
static
/******************************************************************************/
public class Solution {
    public String findContestMatch(int n) {
        TreeNode[] matches = new TreeNode[n];
        for (int i = 0; i < n; i++) {
            matches[i] = new TreeNode(i + 1);
        }
        int len = n;
        while (len > 1) {
            for (int i = 0; i < len / 2; i++) {
                TreeNode newNode = new TreeNode(matches[i].val);
                newNode.left = matches[i];
                newNode.right = matches[len - 1 - i];
                matches[i] = newNode;
            }
            len = len >> 1;
        }
        StringBuilder sb = new StringBuilder();
        dfs(matches[0], sb);
        return sb.toString();
    }

    void dfs(TreeNode root, StringBuilder sb) {
        if (root.left == null && root.right == null) {
            sb.append(root.val);
            return;
        }
        sb.append("(");
        dfs(root.left, sb);
        sb.append(",");
        dfs(root.right, sb);
        sb.append(")");
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        OutputContestMatches.Solution tester = new OutputContestMatches.Solution();
        String[] inputs = {
            "4", "((1,4),(2,3))",
            "8", "(((1,8),(4,5)),((2,7),(3,6)))",
            "16", "((((1,16),(8,9)),((4,13),(5,12))),(((2,15),(7,10)),((3,14),(6,11))))",
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int n = Integer.parseInt(inputs[2 * i]);
            String expected = inputs[1 + 2 * i];
            System.out.println(Printer.seperator());
            String output= tester.findContestMatch(n);
            System.out.println(Printer.wrapColor(n, "magenta") + " -> " + output + Printer.wrapColor(", expected: " + expected, output.equals(expected) ? "green" : "red"));
        }
    }
}

刚刚从easy转型过来确实很不适应, 这个题目刚开始几乎就要放弃了, 不过后来想想还是自己做了. middle的题目做起来确实感觉很不一样, 考察的不再是一个单独类型的知识点, 而且具体考察的是哪个知识点(套路), 也不是那么immediate. 不过做完之后还是觉得非常有意思;

最后的速度是6ms (98%), 出乎意料的好;

本来的想法是做一个UF类的算法, 就有点慌, 因为这个算法我完全没有实现过, 不过后来看了题目要求, 这个题目的union的操作直接自己手动做就行了. 另外一个线索的点就是最后的输出的形式, 一堆括号, 典型的dfs的timestamp/parens结构;

从这题开始, 以后先看discussion的最优解, 然后再看submission的最优解, 因为submission的最优解往往什么说明都没有, 尤其是假如核心的算法我从来没有接触过, 直接看人家的代码是很难理解的. 不如直接先看一圈discussion, 对于一些很slick的核心算法熟悉了之后, 再看submission就会熟悉起来;

另外一个好处就是submission最优解的代码可能会已经出现在discussion, 所以如果在discussion里面先直接用有context和解释的情况下看懂了之后, 就省的自己在submission里叼出来慢慢猜了;

这个是discussion最优解:

public class Solution {  
    public String findContestMatch(int n) {  
        List<String> matches = new ArrayList<>();  
        for(int i = 1; i <= n; i++) matches.add(String.valueOf(i));  

        while(matches.size() != 1){  
            List<String> newRound = new ArrayList<>();  
            for(int i = 0; i < matches.size()/2; i++)     
                newRound.add("(" + matches.get(i) + "," + matches.get(matches.size() - i - 1) + ")");  
            matches = newRound;  
        }  
        return matches.get(0);  
    }  
}

看了他这个代码之后才意识到这个问题的本质其实其实是很简单的, 这里他就按照round来做, 每一个round完成的操作就是从前一个round的所有match(in the form of strings)当中, 取出两个, 括号一包, 然后作为一个新的match(a longer string now)扔到一个新的list里面去; 这个做法的核心思路还是很直接的;

这个是一个更直接的思路:

public class Solution {  
    public String findContestMatch(int n) {  
        String[] m = new String[n];  
        for (int i = 0; i < n; i++) {  
            m[i] = String.valueOf(i + 1);  
        }  

        while (n > 1) {  
            for (int i = 0; i < n / 2; i++) {  
                m[i] = "(" + m[i] + "," + m[n - 1 - i] + ")";  
            }  
            n /= 2;  
        }  

        return m[0];  
    }  
}

这个比上一个快很多: 7(94);

Problem Description

During the NBA playoffs, we always arrange the rather strong team to play with the rather weak team, like make the rank 1 team play with the rank nth team, which is a good strategy to make the contest more interesting. Now, you're given n teams, you need to output their final contest matches in the form of a string.

The n teams are given in the form of positive integers from 1 to n, which represents their initial rank. (Rank 1 is the strongest team and Rank n is the weakest team.) We'll use parentheses('(', ')') and commas(',') to represent the contest team pairing - parentheses('(' , ')') for pairing and commas(',') for partition. During the pairing process in each round, you always need to follow the strategy of making the rather strong one pair with the rather weak one.

Example 1:
Input: 2
Output: (1,2)
Explanation:
Initially, we have the team 1 and the team 2, placed like: 1,2.
Then we pair the team (1,2) together with '(', ')' and ',', which is the final answer.
Example 2:
Input: 4
Output: ((1,4),(2,3))
Explanation:
In the first round, we pair the team 1 and 4, the team 2 and 3 together, as we need to make the strong team and weak team together.
And we got (1,4),(2,3).
In the second round, the winners of (1,4) and (2,3) need to play again to generate the final winner, so you need to add the paratheses outside them.
And we got the final answer ((1,4),(2,3)).
Example 3:
Input: 8
Output: (((1,8),(4,5)),((2,7),(3,6)))
Explanation:
First round: (1,8),(2,7),(3,6),(4,5)
Second round: ((1,8),(4,5)),((2,7),(3,6))
Third round: (((1,8),(4,5)),((2,7),(3,6)))
Since the third round will generate the final winner, you need to output the answer (((1,8),(4,5)),((2,7),(3,6))).
Note:
The n is in range [2, 2^12].
We ensure that the input n can be converted into the form 2^k, where k is a positive integer.
Difficulty:Medium
Total Accepted:3.2K
Total Submissions:4.4K
Contributor: love_Fawn
Companies
google
Related Topics
recursion string