401. 二进制手表

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

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

 

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

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

案例:

输入: 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public class Solution {
    /*
    坑1：
        【小时位置】的范围是0-11，这需要注意，即四个灯不能全亮。
        【分钟位置】同理，分钟位置也有同样的限制。
     坑2：
        小时不能以0开头，但分钟可以。

     思路：
        小时和分钟都有多种亮灯数量。
        如小时2个，分钟3个。小时位置和分钟位置并无关联，它们只受固定范围的约束。
        两层循环解决问题。第一层遍历小时的可能情况，第二层遍历分钟的可能情况。若范围符合，则添加解。
        【注意】小时可以占用全部的灯，分钟都不亮即可。

        小时和分钟的序列可以通过一个二进制数来表示，该数字的十进制表示就是对应的小时数或分钟数。
        小时和分钟序列的变更可以通过二进制数自增实现，若超过范围限制就continue。
        需要有专门的函数来获取二进制数中1的个数，即亮灯数量。

     @param num: 亮灯个数
     */
    private int getCount(int num){
        int cnt = 0, b = 1;
        for (int i = 1; i <= 6; i++) {
            if ((num & b) > 0)
                cnt++;
            b = b << 1;
        }
        return cnt;
    }

    public List<String> readBinaryWatch(int num) {
        List<String> res = new ArrayList<>();

        for (int i = 0; i < 12; i++) { // 小时
            int hourNum = getCount(i); // 获取小时位置亮灯个数
            for (int j = 0; j < 60; j++) { // 分钟
                int minuteNum = getCount(j); // 获取分钟位置的亮灯个数
                if (hourNum + minuteNum > num)
                    continue;
                if (hourNum + minuteNum == num) {
                    if (j < 10)
                        res.add(i + ":0" + j);
                    else
                        res.add(i + ":" + j);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        List<String> list = new Solution().readBinaryWatch(2);
        for (String e : list) {
            System.out.println(e);
        }
    }
}