Google – Team Match

Google – Team Match
有n个player, n是2的倍数，排名1 to n. 每次比赛会让最好的对阵最差的，然后淘汰掉一半人，继续比赛直到只剩一个人位置。
要求返回一个字符串表示整个对阵过程。
比如n = 8, 那么应该return (((1, 8), (4, 5)), ((2, 7), (3, 4)))。
因为第一轮比赛之后胜者为8，7，6，5。 第二轮就应该是(8, 5)和(7, 6)。
[Solution]
这题第一反应应该是recursion。其实这里面有个tail-recursion的概念。
当然Iterative也可以做，但不是很熟练这样的解法，以后需要多练一下。

// Iterative

class Solution {

  public String teamMatch(int n) {

    String[] team = new String[n + 1];

    for (int i = 1; i <= n; i++) {
       team[i] = String.valueOf(i);
     }
     while (n > 1) {

      for (int i = 1; i <= n / 2; i++) {

        team[i] = print(team[i], team[n - i + 1]);

      }

      n /= 2;

    }

    return team[1];

  }

  private String print(String i, String j) {

    return String.format("(%s, %s)", i, j);

  }

}

// tail recursion

class Solution2 {

  public String teamMatch(int n) {

    String[] team = new String[n];

    for (int i = 0; i < n; i++) {

      team[i] = String.valueOf(i + 1);

    }

    return recur(team);

  }

  private String recur(String[] team) {

    if (team.length == 1) {

      return team[0];

    }

    int n = team.length;

    String[] newTeam = new String[n / 2];

    for (int i = 0; i < n / 2; i++) {

      newTeam[i] = String.format("(%s, %s)", team[i], team[n - i - 1]);

    }

    return recur(newTeam);

  }

}

Read full article from Google – Team Match