3ms JAVA code with backtracking. EASY to understand with Explaination


  • 0
    A

    In the beginning, we should know how many light on the top and how many light on the bot.
    top + bot = num;
    First, use backtracking to get the hour part.(top)
    Second, use backtracking to get the minutes part.(bot)
    Third, combine them to the result.

    public List<String> readBinaryWatch(int num) {
        
        if(num == 0)
            return new ArrayList<String>(Arrays.asList("0:00"));
        if(num > 10)
            return new ArrayList<String>();
        List<String> re = new ArrayList<>();
        int[] hour = {1, 2, 4, 8};
        int[] min = {1, 2, 4, 8, 16, 32};
        for(int top = num / 7; top <= 4 && top <= num; top ++){
            int bot = num - top;
            List<String> reHour = new ArrayList<>();
            List<String> reMin = new ArrayList<>();
            bkHour(reHour, 0, top, hour, 0, 0);
            bkMin(reMin, 0, bot, min, 0, 0);
            for(int i = 0; i < reHour.size(); i++){
                String h = reHour.get(i);
                for(int j = 0; j < reMin.size(); j++){
                    re.add(h + reMin.get(j));
                }
            }
        }
        return re;
    }
    public void bkHour(List<String> re, int cur, int top, int[] hour, int level, int times){
        if(times == top){
            if(cur > 11)
                return;
            re.add(cur + ":");
            return;
        }
        for(int i = level; i < hour.length; i++){
            bkHour(re, cur + hour[i], top, hour, i + 1, times + 1);
        }
    }
    public void bkMin(List<String> re, int cur, int bot, int[] min, int level, int times){
        if(times == bot){
            if(cur > 59)
                return;
            if(cur < 10){
                re.add("0" + cur);
            }
            else
                re.add(cur + "");
            return;
        }
        for(int i = level; i < min.length; i++){
            bkMin(re, cur + min[i], bot, min, i + 1, times + 1);
        }
    }

Log in to reply
 

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