401 Binary Watch

401. Binary Watch

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

The order of output does not matter. The hour must not contain a leading zero, for example "01:00" is not valid, it should be "1:00". The minute must be consist of two digits and may contain a leading zero, for example "10:2" is not valid, it should be "10:02".

Company Tag: Google

分析

其实不太懂为什么这道题会标成easy…………感觉分明是combination的升级版嘛

思路就是因为最多会形成6个灯的，所以从0-6生成所有可能的binary组合然后分开组合

代码

public List<String> readBinaryWatch(int num) {
    List<String> res = new ArrayList<>();
    if(num < 0) {
        return res;
    }
    Map<Integer, List<String>> map = new HashMap<>();
    for(int i = 0; i <= num; i++) {
        char[] cur = new char[6];
        Arrays.fill(cur, '0');
        List<String> curRes = new ArrayList<>();
        generate(curRes, 0, 0, i, cur);
        map.put(i, curRes);
    }
    for(int i = 0; i <= num && i <= 4; i++) {
        List<String> hour = map.get(i);
        List<String> min = map.get(num - i);
        for(String h: hour) {
            int hourInt = Integer.parseInt(h, 2);
            if(hourInt >= 12) {
                continue;
            }
            for(String m: min) {
                int minInt = Integer.parseInt(m, 2);
                if(minInt >= 60) {
                    continue;
                }
                StringBuilder sb = new StringBuilder();
                sb.append(hourInt);
                sb.append(':');
                if(minInt <= 9) {
                    sb.append('0');
                }
                sb.append(minInt);
                res.add(sb.toString());
            }
        }
    }
    return res;
}

private void generate(List<String> res, int index, int cnt, int n, char[] cur) {
    if(cnt == n) {
        res.add(new String(cur));
        return;
    }
    for(int i = index; i < 6; i++) {
        cur[i] = '1';
        generate(res, i + 1, cnt + 1, n, cur);
        cur[i]  = '0';
    }
}