E401.二进制手表

brute force, https://leetcode.cn/problems/binary-watch/

二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。

例如，下面的二进制手表读取 "4:51" 。

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

小时不会以零开头：

例如，"01:00" 是无效的时间，正确的写法应该是 "1:00" 。

分钟必须由两位数组成，可能会以零开头：

例如，"10:2" 是无效的时间，正确的写法应该是 "10:02" 。

示例 1：

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

示例 2：

输入：turnedOn = 9
输出：[]

提示：

0 <= turnedOn <= 10

这个问题可以通过枚举法轻松解决。

解题思路

与其去计算哪些 LED 灯亮着，不如直接遍历所有可能的时间（小时从 0 到 11，分钟从 0 到 59），然后计算这个时间的二进制表示中共有多少个 $1$ 。

遍历范围：
- 小时 $h$ ： $0 \leq h < 12$
- 分钟 $m$ ： $0 \leq m < 60$
计算二进制中 1 的个数：
- 在 Python 中，可以使用 bin(n).count('1') 或者更高效的 int.bit_count()（Python 3.10+）。
- 我们需要计算 h 的二进制 1 的个数加上 m 的二进制 1 的个数。
匹配与格式化：
- 如果总个数等于 turnedOn，则按照题目要求的格式 "H:MM" 格式化时间。
- 分钟 m 如果小于 10，需要在前面补零（可以使用 f"{h}:{m:02d}"）。

代码实现

python

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        res = []
        # 遍历所有小时 0-11
        for h in range(12):
            # 遍历所有分钟 0-59
            for m in range(60):
                # 计算小时和分钟二进制中 '1' 的总个数
                # Python 3.10+ 可以直接用 h.bit_count() + m.bit_count()
                if bin(h).count('1') + bin(m).count('1') == turnedOn:
                    # 格式化时间，m:02d 表示分钟不足两位时前面补 0
                    res.append(f"{h}:{m:02d}")
        return res

复杂度分析

时间复杂度： $O (1)$ 。虽然代码中有嵌套循环，但循环次数是固定的（ $12 \times 60 = 720$ 次）。这是一个常数级的操作。
空间复杂度： $O (1)$ 。除了存储答案的列表外，我们只使用了常数级别的额外空间。

为什么选择这种方法？

虽然也可以使用回溯算法（搜索哪些 LED 被点亮），但回溯的逻辑相对复杂，需要处理“小时不能超过 11”和“分钟不能超过 59”的边界条件。而直接枚举所有时间的方法逻辑最清晰，代码最简洁，且由于总状态数极少（仅 720 种），运行速度非常快。

E401.二进制手表 ​

E401.二进制手表