Java code, bottomUp fashion, pure string processing thus slow


  • 0
    A
    class Solution {
    public String findContestMatch(int n) {
        // algorithm 2017/08/31: simply expand the team representation from smaller to larger
        //  observation: (1,2) => ((1,4),(2,3)) => (((1,8),(4,5)),((2,7),(3,6))) 
        //  essentially each time when we double the teams, the existing team is replaced with "(<teamNo>,<buddyTeamNo>)"
        String teams = "(1,2)";
        int    num   = 2;
        while (num < n) {
            teams = doubledTeams(teams, num);
            num <<= 1;
        }
        return teams;
    }
    
    private StringBuilder doubledTeams(StringBuilder teams, int currentNum) {
        int doubledNum        = currentNum << 1;
        int strLen            = teams.length();
        StringBuilder builder = new StringBuilder();
        int teamNo            = 0;
        
        for (int index = 0; index < strLen; index++) {
            char ch = teams.charAt(index); 
            if ('(' == ch) {                    // (
                builder.append(ch); 
            } else if (',' == ch || ')' == ch) {  // , or )
                if (0 != teamNo) {
                    String replacementTeam = String.format("(%d,%d)", teamNo, doubledNum+1-teamNo);
                    builder.append(replacementTeam);
                    teamNo = 0;
                }
                builder.append(ch);
            } else {    // digit
                teamNo = teamNo * 10 + (ch - '0');
            }
        }
        return builder.toString();
    }
    

    }


Log in to reply
 

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