二进制手表

力扣 401. 二进制手表

题目说明

二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。
- 例如，下面的二进制手表读取 "3:25" 。
（图源：WikiMedia - Binary clock samui moon.jpg ，许可协议：Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0) ）

给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。

小时不会以零开头：
- 例如，"01:00" 是无效的时间，正确的写法应该是 "1:00" 。
分钟必须由两位数组成，可能会以零开头：
- 例如，"10:2" 是无效的时间，正确的写法应该是 "10:02" 。

示例

示例 1：

1 2	输入：turnedOn = 1 输出：["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

示例 2：

1 2	输入：turnedOn = 9 输出：[]

笔者理解

此题是一道位运算算法问题，在力扣题库中被定义为简单题。

解法

当笔者阅读完此题后，发现此题可以转化成经典的位运算题目，让我们来看看具体如何实现的吧。

实现

class Solution {
    /*
     * 位运算
     */
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> result = new ArrayList<String>();
        StringBuilder sb = new StringBuilder();

        // 亮灯数超过8就溢出了，没有这样的时间
        if(turnedOn > 8) {
            return result;
        }

        // 由于时间的可能比较小，可以直接对每个时间进行验证，判断是否符合亮灯数
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                if (count(h) + count(m) == turnedOn) {
                    sb.append(h);
                    sb.append(":");
                    // 分钟的前置0
                    if (m < 10) {
                        sb.append(0);
                    }
                    sb.append(m);

                    result.add(sb.toString());
                }
                // 清空，方便再次存储
                sb.delete(0, sb.length());
            }
        }

        return result;

    }

    /*
     * 计算当前数 二进制数中1的个数
     */
    public int count(int n) {
        int nums = 0;
        while (n != 0) {
            n &= (n - 1);
            nums++;
        }
        return nums;
    }
}