Java 10 lines


  • 20
    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);
        }
    }
    

  • 15
    L

    Same idea. Indeed, we can even do this in an in-place fashion.

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

    Furthermore, if one uses a LinkedList to implement the string, the code can run in O(n) time.
    Update: The (long) implementation is shown as follows, which uses the ListNode that is pre-defined by LeetCode.

    private ListNode[] intToList(int n) {
        ListNode head = null, tail = null;
        if (n == 0) head = tail = new ListNode('0');
        else {
            while (n > 0) {
                ListNode p = new ListNode(n % 10 + '0');
                p.next = head;
                head = p;
                n /= 10;
    
                if (tail == null) tail = head;
            }
        }
        return new ListNode[]{head, tail};
    }
    
    public String findContestMatch(int n) {
    
        ListNode[] heads = new ListNode[n];
        ListNode[] tails = new ListNode[n];
        for (int i = 0; i < n; i++) {
            ListNode[] list = intToList(i + 1);
            heads[i] = list[0];
            tails[i] = list[1];
        }
    
        for (; n > 1; n /= 2)
            for (int i = 0; i < n / 2; i++) {
                ListNode leftParen = new ListNode('(');
                ListNode comma = new ListNode(',');
                ListNode rightParen = new ListNode(')');
    
                leftParen.next = heads[i];
                tails[i].next = comma;
                comma.next = heads[n - 1 - i];
                tails[n - 1 - i].next = rightParen;
    
                heads[i] = leftParen;
                tails[i] = rightParen;
            }
    
        StringBuilder builder = new StringBuilder();
        for (ListNode p = heads[0]; p != null; p = p.next)
            builder.append((char) p.val);
        return builder.toString();
    }
    

  • 9

    @lixx2100 same here, in place as well, using 2 pointer instead of for loops.

        public string FindContestMatch(int n) {
            string[] arr = new string[n];
            for (int i = 0; i < n; i++) arr[i] = (i + 1).ToString();
            
            int left = 0;
            int right = n - 1;
            while (left < right)
            {
                while (left < right)
                {
                    arr[left] = "(" + arr[left] + "," + arr[right] + ")";
                    left++;
                    right--;
                }
                left = 0;
            }
            
            return arr[0];
        }
    

  • 0
    W

    @lixx2100

    So far I've only seen lots of O(nlogn) solutions...

    I think in terms of O(n), you need to figure out how many parentheses you need to add on the left/right of each number.

    Using backtracking will always need O(logn) times of looping through the whole list.


  • 0
    L

    @whglamrock If we assume string concatenation takes O(1) time, the above code runs in O(n) time, since the runtime is the sum of the geometric sequence n/2, n/4, ..., 4, 2, 1.

    Now, if we store each number in a doubly linked list node, string concatenation is just like merging two linked lists, which can be done in O(1) time. There are n numbers in total, and at most 3n extra nodes will be created, for those (, ,, ), resulting a total runtime/space of O(4n) = O(n).


  • 0
    W

    @lixx2100 correct me if I am wrong

    At first, n/2 + n/4 + ... + 4 + 2 + 1 is O(logN) time, not O(N).

    Second, I don't know how you jump to the conclusion that one number only needs one "(", one ")" and one ",". If you could give logical deduction I would really appreciate.

    Third, the string concatenation surely takes O(N) because we need to recreate a new string. In terms of using doubly-linked list, you need to justify the above point ("3 extra" nodes for each number), otherwise you cannot guarantee how many "(" or ")" you need to put on each side of the number.


  • 0
    L

    @whglamrock First, n/2 + n/4 + ... + 4 + 2 + 1 = O(n). Even the first term n/2 is significantly greater than O(log n). When n is a power of 2, n/2 + n/4 + ... + 4 + 2 + 1 = n - 1.

    Regarding your second and third question, I will write an implementation later today. And I guess the code would be better self-explanatory.

    Update: I had an implementation in my original post, which runs in O(n) time. String concatenations there are "achieved" by linked list concatenations, which take O(1) time.


  • 0
    W

    @lixx2100

    Sorry I didn't make it clear...

    Everybody knows how to calculate n/2 + n/4 + n/8 + ... + 4 + 2 + 1 since it is a simple geometric sequence. I was saying it has O(logN) items whereas the number of items decides the number of loops (in your linked-list case, the concatenation of nodes).

    However, if you can prove that each number needs exactly three extra chars, then we can ignore, jump out of the above discussion because what matters then will be the total number of operations, which is the sum of (n/2 + n/4 + n/8 + ... + 4 + 2 + 1).


  • 0
    L

    @whglamrock Just observe the number of (, ,, ) in the final output is also equal to n/2 + n/4 + ... + 4 + 2 + 1 = n - 1. Therefore, in total we have exactly 3n - 3 extra characters.
    If you like, you can say, in an average case, each number requires no more than 3 chars.


  • 0
    W

    @lixx2100

    You are right about the maximum number of extra chars. I see mathematically, the limit value for total chars needed is 3 * (n - 1) when n goes towards infinitely great.

    But I still wonder how you can manage to code it :)


  • 1

    Recursion use Deque.

        public String findContestMatch(int n) {
          Deque<String> deque = new ArrayDeque();
          for(int i = 1; i <= n; i++){
            deque.addLast(String.valueOf(i));  
          }
          return helper(deque);  
        }
        
        String helper(Deque<String> deque){
            if(deque.size() == 1) return deque.pollFirst();
            Deque<String> newDeque = new ArrayDeque();
            while(!deque.isEmpty()){
              newDeque.addLast("(" + deque.pollFirst() + "," + deque.pollLast() + ")");   
            }
            return helper(newDeque);
        }

  • 1
    W

    Iterative version.

    public class Solution {
        public String findContestMatch(int n) {
            Deque<String> queue = new ArrayDeque<>();
            for (int i = 1; i <= n; i++) {
                queue.offer(String.valueOf(i));
            }
            
            while (queue.size() > 1) {
                Deque<String> nextQueue = new ArrayDeque<>();
                while (!queue.isEmpty()) {
                    nextQueue.offer("(" + queue.poll() + "," + queue.pollLast() + ")");    
                }
                queue = nextQueue;
            }
            return queue.poll();
        }
    }
    

Log in to reply
 

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