二进制手表

题目

二进制手表顶部有 4 个 LED 代表小时（0-11），底部的 6 个 LED 代表分钟（0-59）。

每个 LED 代表一个 0 或 1，最低位在右侧。

例如，上面的二进制手表读取 “3:25”。

给定一个非负整数 n代表当前 LED 亮着的数量，返回所有可能的时间。

案例:

image

输入: n = 1
返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

注意事项:

输出的顺序没有要求。
小时不会以零开头，比如 “01:00”是不允许的，应为 “1:00”。
分钟必须由两位数组成，可能会以零开头，比如 “10:2”是无效的，应为 “10:02”。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-watch
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 思路一
  • 可以将小时和分钟重复遍历,找出当前时间点对应的二进制位有多少个1,此时就是符合条件的,输出即可.
• 思路二
  • 领扣上看到的,将上下两个表盘的所有可能性列出.然后根据传入的num来依次判断,最后输出

代码

class Solution {
    public List<String> readBinaryWatch(int num) {
        //要计算所有的可能性,可以将小时和分钟的所有可能做循环,然后将当前点数的二进制值相加看有几个1,如果符合num,则对应输出时间
        List<String> result = new ArrayList<>();
        for(int i = 0;i < 12;i++){
            for(int h = 0;h < 60;h++){
                if((getNumForOne(i) + getNumForOne(h)) == num){
                    String hString = h<10?"0"+h:h+"";
                    result.add(i+":"+hString);
                }
            }
        }
        return result;
    }
    
    private int getNumForOne(int n){
        int sum = 0;
        for(int i = 0;i < 32;i++){
            if((1&(n>>i)) == 1){
                sum++;
            }
        }
        return sum;
    }
}

枚举法

class Solution {
    public List<String> readBinaryWatch(int num) {
        if (num > 8) {
            return new ArrayList<>();
        }

        String[] topZero = new String[]{"0"};
        String[] topOne = new String[]{"1", "2", "4", "8"};
        String[] topTwo = new String[]{"3", "5", "9", "6", "10"};
        String[] topThree = new String[]{"7","11"};

        String[] endZero = new String[]{":00"};
        String[] endOne = new String[]{":01", ":02", ":04", ":08", ":16", ":32"};
        String[] endTwo = new String[]{
                ":03", ":05", ":09", ":17", ":33",
                ":06", ":10", ":18", ":34",
                ":12", ":20", ":36",
                ":24", ":40",
                ":48"};
        String[] endThree = new String[]{
                ":07", ":11", ":19", ":35",
                ":13", ":21", ":37",
                ":25", ":41",
                ":49",
                ":14", ":22", ":38",
                ":26", ":42",
                ":50",
                ":28", ":44",
                ":52",
                ":56"};
        String[] endFour = new String[]{
                ":58", ":54", ":46", ":30",
                ":57", ":53", ":45", ":29",
                ":51", ":43", ":27",
                ":39", ":23",
                ":15"};

        String[] endFive = new String[]{":59", ":55", ":47", ":31"};


        List<String> result = new ArrayList<>();
        int hour = 0, minute = num - hour;
        while (hour < 4 && minute >= 0) {
            if (minute > 5) {
                hour++;
                minute = num - hour;
                continue;
            }
            String[] hourStr, minuteStr;
            switch (hour) {
                case 0: hourStr = topZero;break;
                case 1: hourStr = topOne;break;
                case 2: hourStr = topTwo;break;
                case 3: hourStr = topThree;break;
                default: hourStr = topZero;break;
            }

            switch (minute) {
                case 0: minuteStr = endZero;break;
                case 1: minuteStr = endOne;break;
                case 2: minuteStr = endTwo;break;
                case 3: minuteStr = endThree;break;
                case 4: minuteStr = endFour;break;
                case 5: minuteStr = endFive;break;
                default: minuteStr = endZero;break;
            }
            sum(result,hourStr,minuteStr);

            hour++;
            minute = num - hour;
        }
        return result;
    }
    
    private static void sum(List<String> result, String[] hour, String[] minute) {
        for (String h : hour) {
            for (String m : minute) {
                result.add(h+m);
            }
        }
    }
}