1. 项目概述今天想和大家分享一道LeetCode上的有趣题目——401.二进制手表。这是一道被标记为简单级别的题目但其中蕴含的二进制思维和组合算法却非常值得玩味。题目要求我们根据给定的LED灯点亮数量输出所有可能表示的时间组合。这道题出现在LeetCode的位运算分类中但实际解题时可以完全不使用位运算。我在第一次尝试时就被这个简单标签给骗了花了比预期多得多的时间才找到最优解。下面我就来详细拆解这道题的解题思路和实现方法。2. 题目理解与需求分析2.1 题目描述二进制手表顶部有4个LED代表小时(0-11)底部有6个LED代表分钟(0-59)。每个LED代表一个0或1最右侧的LED是最低位。给定一个非负整数n表示当前亮着的LED数量返回所有可能的时间组合。示例 输入n 1 输出[1:00, 2:00, 4:00, 8:00, 0:01, 0:02, 0:04, 0:08, 0:16, 0:32]2.2 核心需求解析这道题的核心在于理解二进制手表的显示原理枚举所有可能的LED灯组合过滤出符合时间格式的有效组合将二进制表示转换为标准时间格式关键在于如何高效地枚举所有可能的组合而不会产生重复或无效的结果。3. 解题思路与算法选择3.1 暴力枚举法最直观的思路是枚举所有可能的小时和分钟组合然后计算每个组合中1的位数是否等于给定的n。def readBinaryWatch(self, num: int) - List[str]: res [] for h in range(12): for m in range(60): if bin(h).count(1) bin(m).count(1) num: res.append(f{h}:{m:02d}) return res这种方法简单直接但由于小时和分钟的范围都很小(小时0-11分钟0-59)所以时间复杂度实际上是O(1)。3.2 组合优化法更高效的解法是预先生成所有可能的小时和分钟组合然后根据给定的n进行匹配。预计算0-11中每个数字的二进制1的个数预计算0-59中每个数字的二进制1的个数对于给定的n遍历所有可能的小时h和分钟m组合使得h的1的个数 m的1的个数 ndef readBinaryWatch(self, num: int) - List[str]: def count_bits(n): return bin(n).count(1) hour_bits [count_bits(h) for h in range(12)] minute_bits [count_bits(m) for m in range(60)] res [] for h in range(12): for m in range(60): if hour_bits[h] minute_bits[m] num: res.append(f{h}:{m:02d}) return res这种方法通过预处理减少了重复计算虽然时间复杂度仍然是O(1)但实际运行效率会更高。3.3 位运算解法虽然题目与二进制相关但位运算并不是必须的。不过为了完整性这里也提供一个使用位运算的解法def readBinaryWatch(self, num: int) - List[str]: res [] for h in range(12): for m in range(60): if (h 3) (h 2 1) (h 1 1) (h 1) \ (m 5) (m 4 1) (m 3 1) (m 2 1) (m 1 1) (m 1) num: res.append(f{h}:{m:02d}) return res这种方法通过移位和与运算来计算1的位数虽然看起来更二进制但实际上可读性较差性能提升也不明显。4. 代码实现与优化4.1 Python实现综合以上分析我认为组合优化法是最佳选择。下面是完整的Python实现def readBinaryWatch(num: int) - List[str]: def count_bits(n): count 0 while n: n n - 1 count 1 return count # 预计算所有可能的小时和分钟的1的个数 hours [[] for _ in range(5)] # 小时最多4个1 for h in range(12): bits count_bits(h) hours[bits].append(h) minutes [[] for _ in range(7)] # 分钟最多6个1 for m in range(60): bits count_bits(m) minutes[bits].append(m) res [] for h_bits in range(min(num 1, 5)): # 小时可能的1的个数 m_bits num - h_bits if m_bits 0 or m_bits 6: continue for h in hours[h_bits]: for m in minutes[m_bits]: res.append(f{h}:{m:02d}) return res这个实现有几个优化点使用更高效的位计数方法(n n - 1)预先按1的个数分类存储小时和分钟直接组合符合条件的小时和分钟避免无效遍历4.2 复杂度分析时间复杂度O(1)因为所有循环的次数都是固定的(小时0-11分钟0-59)空间复杂度O(1)只需要常数空间存储预计算结果5. 测试用例与边界条件5.1 常规测试用例print(readBinaryWatch(1)) # 输出[0:01, 0:02, 0:04, 0:08, 0:16, 0:32, 1:00, 2:00, 4:00, 8:00] print(readBinaryWatch(2)) # 输出包含0:03, 0:05, 0:06, ..., 3:00, 5:00, 6:00, 9:00, 10:005.2 边界条件n 0只有0:00一种可能n 8最大可能值(4小时LED 6分钟LED 10但n8时仍有解)n 8无解返回空列表print(readBinaryWatch(0)) # [0:00] print(readBinaryWatch(8)) # [7:31, 7:47, 7:55, 7:59, 11:31, 11:47, 11:55, 11:59] print(readBinaryWatch(9)) # []6. 常见问题与解决技巧6.1 时间格式处理分钟数需要格式化为两位数可以使用Python的f-stringf{h}:{m:02d}或者使用format函数{}:{:02d}.format(h, m)6.2 无效组合过滤需要注意小时和分钟的有效范围小时0-11分钟0-59在暴力枚举法中循环范围已经限制了有效性。但在其他解法中需要特别注意。6.3 性能优化技巧预处理1的个数可以显著提高性能使用位运算计算1的个数比bin().count(1)更快提前终止不可能的组合(如h_bits 4或m_bits 6)6.4 其他语言实现对于C或Java等语言可以使用内置的位计数函数C: __builtin_popcountJava: Integer.bitCount7. 算法扩展与变种7.1 十进制数字手表如果手表使用十进制显示题目可以改为给定数字和为n的所有时间组合。解法思路类似只是将二进制1的计数改为数字各位的和。7.2 多LED手表如果手表有更多LED灯或者小时/分钟的表示范围更大暴力枚举法可能不再适用需要考虑更高效的组合生成算法。7.3 反向问题给定一个时间计算亮着的LED数量。这可以直接使用位计数函数解决。def count_leds(time_str): h, m map(int, time_str.split(:)) return bin(h).count(1) bin(m).count(1)8. 实际应用与思考虽然这道题看起来只是一个编程练习但它实际上训练了几个重要的编程思维问题分解将时间表示分解为小时和分钟两部分组合思维理解不同LED组合产生的结果预处理优化通过预计算提高效率边界条件处理考虑所有可能的输入情况这些技能在实际开发中非常有用特别是在处理组合配置、权限控制等场景时。