OutputContestMatchesOPT [source code]

public class OutputContestMatchesOPT {
static
/******************************************************************************/
public class Solution {
    public String findContestMatch(int n) {
        StringBuilder sb = new StringBuilder();
        helper(sb, 3, n, 1);
        return sb.toString();
    }

    void helper(StringBuilder sb, int sum, int n, int val) {
        if (sum > n + 1) {
            sb.append(val);
            return;
        }
        sb.append('(');
        helper(sb, (sum << 1) - 1, n, val);
        sb.append(',');
        helper(sb, (sum << 1) - 1, n, sum - val);
        sb.append(')');        
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        OutputContestMatchesOPT.Solution tester = new OutputContestMatchesOPT.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"));
        }
    }
}

这个是submission最优解: 4(99), 思路跟我的做法相似, 但是简洁了不少;

这个作者也没有留下任何的解释, 所以还是得自己猜每个变量/参数的意思; 除了根据变量的名字来猜, 还要看的就是这个变量被update和access的地方. 这里是一个recursion, 所以在recursion里面观察arguments如何变化也很重要;

这里他这个DFS背后的tree其实跟我的是一样的; 他可能就是在观察出来这个tree之后, 直接避免explicit简历这个tree和node, 而是直接通过数字上的DFS来完成;

这里的sum, 其实就是一个tag. 这个tag是跟depth对应的. 但是为什么不用depth? 因为这个sum后面是要参与每一个node的val的计算的; 因为这里他没有explicit的node, 所以也就没有办法用attribute来保存val这样的信息; 但是我们在走DFS的时候, 每一个call实际上还是一个visit to node, 所以当我们进入这个call的时候, 我们必须要有这个node的val. 但是这个node自己又没有办法存储这个val(因为这个node根本没有被建立), 所以唯一的办法就是直接用类似accum和tag的方式, 将这些信息直接保存在recursive call arguments里面. Whenever we are in a call, we can have the information corresponding to this node from the calling arguments;

这里他这个sum就是要做到这个作用, 所以单纯的用depth可能不太好, 因为这里他sum的作用是一个随着depth指数级增长的值. 当然你也可以就用depth来tag, 然后每一个depth一个pow计算一下, 但是这样不如没一层一个*2这样的操作快;

val其实就是当前node的val. 反正总体感觉他这个算法就是一个比较精简的优化; 值得学习, 但是掌握好我自己的这个算法我认为更有利于实际的面试;

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