My Java AC solution with both iteration and recursion. (both arround 11ms).


  • 0
    B
    // Analyzation: Take n = 8 as an example, in first round we should make a list like this: (1,8) (2,7) (3,6) (4,5)
    // Second round: we regard these 4 pair as A, B, C, D, and we will get (A,D) (B,C)
    // Last round we will get the final answer: (X, Y), which X = (A, D) and Y = (B, C)
    // Recursion
    public class Solution {
        public String findContestMatch(int n) {
            List<String> res = new ArrayList<>();
            for (int i = 1; i <= n; i++) res.add(i+"");
            return helper(res);
        }
        private String helper(List<String> res){
            int size = res.size();
            if (size == 1) return res.get(0);
            List<String> newPair = new ArrayList<>();
            for (int i = 0; i < size/2; i++){
                StringBuilder sb = new StringBuilder();
                sb.append("(").append(res.get(i)).append(",").append(res.get(size-i-1)).append(")");
                newPair.add(sb.toString());
            }
            return helper(newPair);
        }
    }
    
    // Iteration
    public class Solution {
        public String findContestMatch(int n) {
            List<String> res = new ArrayList<>();
            for(int i = 1; i <= n; i++) res.add(i+"");
            int size = res.size(), index;
            while (size != 1){
                index = 0;
                List<String> newPair = new ArrayList<>();
                while(index < size/2){
                    StringBuilder sb = new StringBuilder();
                    sb.append("(").append(res.get(index)).append(",").append(res.get(size-index-1)).append(")");
                    newPair.add(sb.toString());
                    index++;
                }
                res = newPair;
                size = res.size();
            }
            return res.get(0);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.