1. 问题背景与理解第一次看到LeetCode 401这道二进制手表的题目时我以为是考察硬件编程或者嵌入式开发。实际上这是一道伪装成硬件问题的经典算法题考察的是组合数学和位运算的应用。题目要求我们列出所有可能的时间表示其中小时(0-11)和分钟(0-59)的二进制形式中1的个数之和等于给定的亮灯数。这个题目巧妙地将时间表示与二进制结合起来我特别喜欢这种将现实场景抽象为算法问题的设计。它不像某些纯数学题那样枯燥而是让我们在解决实际问题的过程中掌握核心算法思想。2. 解题思路分析2.1 暴力枚举法最直观的解法就是枚举所有可能的时间组合然后检查哪些组合满足亮灯数的要求。具体来说遍历所有可能的小时(0-11)对于每个小时遍历所有可能的分钟(0-59)计算当前小时和分钟的二进制表示中1的个数总和如果总和等于给定的亮灯数就将这个时间加入结果列表这种方法的时间复杂度是O(12*60)O(720)在LeetCode的约束条件下完全够用。虽然看起来有点暴力但对于这个问题规模来说是最简单可靠的解法。2.2 位运算优化我们可以用位运算来优化1的个数的计算。在C中可以使用__builtin_popcount函数Java中可以使用Integer.bitCountPython中可以使用bin(x).count(1)。例如计算5的二进制表示中1的个数5的二进制是101bin(5).count(1) 2这种优化虽然在大O表示法上没有改变时间复杂度但实际运行时会更快因为CPU有专门的指令来处理位运算。2.3 组合数学方法更高级的解法是使用组合数学。我们可以遍历所有可能的亮灯数分配方式小时亮灯数k分钟亮灯数num-k对于每种分配找出所有二进制表示有k个1的小时找出所有二进制表示有(num-k)个1的分钟将这些组合起来形成有效时间这种方法避免了无效的枚举理论上更高效但实现起来稍微复杂一些。3. 代码实现与解析3.1 Python实现def readBinaryWatch(num): def count_bits(n): return bin(n).count(1) result [] for h in range(12): for m in range(60): if count_bits(h) count_bits(m) num: result.append(f{h}:{m:02d}) return result这个实现非常直观定义了一个辅助函数count_bits来计算数字的二进制表示中1的个数双重循环枚举所有可能的小时和分钟检查亮灯数是否匹配格式化时间字符串注意分钟要补零3.2 Java实现import java.util.*; public class Solution { public ListString readBinaryWatch(int num) { ListString result new ArrayList(); for (int h 0; h 12; h) { for (int m 0; m 60; m) { if (Integer.bitCount(h) Integer.bitCount(m) num) { result.add(String.format(%d:%02d, h, m)); } } } return result; } }Java实现使用了Integer.bitCount这个内置方法它是用高效的位操作实现的性能很好。3.3 C实现#include vector #include string #include bitset using namespace std; vectorstring readBinaryWatch(int num) { vectorstring result; for (int h 0; h 12; h) { for (int m 0; m 60; m) { if (bitset10(h 6 | m).count() num) { result.push_back(to_string(h) : (m 10 ? 0 : ) to_string(m)); } } } return result; }C版本使用了bitset来高效计算1的个数。这里有个技巧将小时和分钟合并成一个10位数小时占高4位分钟占低6位然后用bitset一次性计算总亮灯数。4. 复杂度分析与优化4.1 时间复杂度暴力枚举法的时间复杂度是O(12*60)O(720)这是一个常数时间复杂度因为无论输入是什么我们都要遍历所有可能的时间组合。4.2 空间复杂度空间复杂度是O(1)的额外空间不考虑输出结果因为我们只需要常数级别的额外空间来存储临时变量。4.3 可能的优化虽然暴力法已经足够好但我们还可以做一些优化预计算所有数字的亮灯数存储在一个数组中避免重复计算使用组合数学方法提前生成有效的小时和分钟组合对于无效的亮灯数如8可以直接返回空列表5. 边界条件与测试用例5.1 特殊输入处理num0只有0:00一个解num8无解因为最大亮灯数是小时(3亮灯) 分钟(5亮灯) 8num0无效输入应该返回空列表5.2 典型测试用例测试用例1num1 期望输出[0:01,0:02,0:04,0:08,0:16,0:32,1:00,2:00,4:00,8:00] 测试用例2num2 期望输出应包含0:03,0:05,0:06,0:09,0:10,0:12,0:17,0:18,0:20,0:24,0:33,0:34,0:36,0:40,0:48,1:01,1:02,1:04,1:08,1:16,1:32,2:01,2:02,2:04,2:08,2:16,2:32,3:00,4:01,4:02,4:04,4:08,4:16,4:32,5:00,6:00,8:01,8:02,8:04,8:08,8:16,8:32,9:00,10:00] 测试用例3num8 期望输出[7:31,7:47,7:55,7:59,11:31,11:47,11:55,11:59]6. 常见错误与调试技巧6.1 常见错误分钟格式化错误忘记补零如1:2而不是1:02亮灯数计算错误特别是使用位运算时可能出错边界条件处理不当如num0或num8的情况无效时间包含如小时11或分钟596.2 调试技巧打印中间结果在循环中打印当前小时、分钟和亮灯数单元测试为count_bits函数单独编写测试小规模测试先用num1这样的小输入验证基本逻辑对比输出与预期输出对比找出差异点7. 算法扩展与变种7.1 类似问题二进制手表II给定亮灯数返回所有可能的时间就是本题二进制手表I给定时间返回亮灯数更简单数字的二进制表示中1的个数191. Number of 1 Bits7.2 进阶思考如果LED可以显示24小时制如何修改算法如果手表有更多LED如秒数如何扩展解法如何高效生成所有满足条件的组合而不是暴力枚举8. 实际应用场景虽然这个问题看起来有点抽象但它实际上体现了几个重要的编程概念位运算的应用如何高效计算二进制表示中1的个数组合问题的解法如何系统地枚举所有可能组合问题抽象能力将现实问题转化为算法问题这些技能在嵌入式开发、密码学、数据压缩等领域都有实际应用。例如在嵌入式系统中我们经常需要检查或设置特定的位在密码学中计算汉明重量1的个数是一个基本操作。9. 个人心得与建议在解决这个问题时我有几点体会不要被题目描述迷惑看似硬件问题实则是算法题从简单方法开始暴力法虽然笨但往往是最可靠的起点善用语言特性不同语言提供的位运算工具可以简化代码注意输出格式特别是时间格式化这种细节容易出错对于刷题建议我认为这道题适合用来练习位运算基础组合问题的枚举方法边界条件处理代码的清晰性和正确性最后提醒一点在面试中遇到这类问题时一定要先和面试官确认输入输出的具体要求比如时间格式、异常处理等这能展现你的沟通能力和严谨性。 
长河君 · 2026/10/29 13:02:25 · 阅读 1.2k LeetCode 401：二进制手表的算法解析与实现
1. 问题背景与理解第一次看到LeetCode 401这道二进制手表的题目时我以为是考察硬件编程或者嵌入式开发。实际上这是一道伪装成硬件问题的经典算法题考察的是组合数学和位运算的应用。题目要求我们列出所有可能的时间表示其中小时(0-11)和分钟(0-59)的二进制形式中1的个数之和等于给定的亮灯数。这个题目巧妙地将时间表示与二进制结合起来我特别喜欢这种将现实场景抽象为算法问题的设计。它不像某些纯数学题那样枯燥而是让我们在解决实际问题的过程中掌握核心算法思想。2. 解题思路分析2.1 暴力枚举法最直观的解法就是枚举所有可能的时间组合然后检查哪些组合满足亮灯数的要求。具体来说遍历所有可能的小时(0-11)对于每个小时遍历所有可能的分钟(0-59)计算当前小时和分钟的二进制表示中1的个数总和如果总和等于给定的亮灯数就将这个时间加入结果列表这种方法的时间复杂度是O(12*60)O(720)在LeetCode的约束条件下完全够用。虽然看起来有点暴力但对于这个问题规模来说是最简单可靠的解法。2.2 位运算优化我们可以用位运算来优化1的个数的计算。在C中可以使用__builtin_popcount函数Java中可以使用Integer.bitCountPython中可以使用bin(x).count(1)。例如计算5的二进制表示中1的个数5的二进制是101bin(5).count(1) 2这种优化虽然在大O表示法上没有改变时间复杂度但实际运行时会更快因为CPU有专门的指令来处理位运算。2.3 组合数学方法更高级的解法是使用组合数学。我们可以遍历所有可能的亮灯数分配方式小时亮灯数k分钟亮灯数num-k对于每种分配找出所有二进制表示有k个1的小时找出所有二进制表示有(num-k)个1的分钟将这些组合起来形成有效时间这种方法避免了无效的枚举理论上更高效但实现起来稍微复杂一些。3. 代码实现与解析3.1 Python实现def readBinaryWatch(num): def count_bits(n): return bin(n).count(1) result [] for h in range(12): for m in range(60): if count_bits(h) count_bits(m) num: result.append(f{h}:{m:02d}) return result这个实现非常直观定义了一个辅助函数count_bits来计算数字的二进制表示中1的个数双重循环枚举所有可能的小时和分钟检查亮灯数是否匹配格式化时间字符串注意分钟要补零3.2 Java实现import java.util.*; public class Solution { public ListString readBinaryWatch(int num) { ListString result new ArrayList(); for (int h 0; h 12; h) { for (int m 0; m 60; m) { if (Integer.bitCount(h) Integer.bitCount(m) num) { result.add(String.format(%d:%02d, h, m)); } } } return result; } }Java实现使用了Integer.bitCount这个内置方法它是用高效的位操作实现的性能很好。3.3 C实现#include vector #include string #include bitset using namespace std; vectorstring readBinaryWatch(int num) { vectorstring result; for (int h 0; h 12; h) { for (int m 0; m 60; m) { if (bitset10(h 6 | m).count() num) { result.push_back(to_string(h) : (m 10 ? 0 : ) to_string(m)); } } } return result; }C版本使用了bitset来高效计算1的个数。这里有个技巧将小时和分钟合并成一个10位数小时占高4位分钟占低6位然后用bitset一次性计算总亮灯数。4. 复杂度分析与优化4.1 时间复杂度暴力枚举法的时间复杂度是O(12*60)O(720)这是一个常数时间复杂度因为无论输入是什么我们都要遍历所有可能的时间组合。4.2 空间复杂度空间复杂度是O(1)的额外空间不考虑输出结果因为我们只需要常数级别的额外空间来存储临时变量。4.3 可能的优化虽然暴力法已经足够好但我们还可以做一些优化预计算所有数字的亮灯数存储在一个数组中避免重复计算使用组合数学方法提前生成有效的小时和分钟组合对于无效的亮灯数如8可以直接返回空列表5. 边界条件与测试用例5.1 特殊输入处理num0只有0:00一个解num8无解因为最大亮灯数是小时(3亮灯) 分钟(5亮灯) 8num0无效输入应该返回空列表5.2 典型测试用例测试用例1num1 期望输出[0:01,0:02,0:04,0:08,0:16,0:32,1:00,2:00,4:00,8:00] 测试用例2num2 期望输出应包含0:03,0:05,0:06,0:09,0:10,0:12,0:17,0:18,0:20,0:24,0:33,0:34,0:36,0:40,0:48,1:01,1:02,1:04,1:08,1:16,1:32,2:01,2:02,2:04,2:08,2:16,2:32,3:00,4:01,4:02,4:04,4:08,4:16,4:32,5:00,6:00,8:01,8:02,8:04,8:08,8:16,8:32,9:00,10:00] 测试用例3num8 期望输出[7:31,7:47,7:55,7:59,11:31,11:47,11:55,11:59]6. 常见错误与调试技巧6.1 常见错误分钟格式化错误忘记补零如1:2而不是1:02亮灯数计算错误特别是使用位运算时可能出错边界条件处理不当如num0或num8的情况无效时间包含如小时11或分钟596.2 调试技巧打印中间结果在循环中打印当前小时、分钟和亮灯数单元测试为count_bits函数单独编写测试小规模测试先用num1这样的小输入验证基本逻辑对比输出与预期输出对比找出差异点7. 算法扩展与变种7.1 类似问题二进制手表II给定亮灯数返回所有可能的时间就是本题二进制手表I给定时间返回亮灯数更简单数字的二进制表示中1的个数191. Number of 1 Bits7.2 进阶思考如果LED可以显示24小时制如何修改算法如果手表有更多LED如秒数如何扩展解法如何高效生成所有满足条件的组合而不是暴力枚举8. 实际应用场景虽然这个问题看起来有点抽象但它实际上体现了几个重要的编程概念位运算的应用如何高效计算二进制表示中1的个数组合问题的解法如何系统地枚举所有可能组合问题抽象能力将现实问题转化为算法问题这些技能在嵌入式开发、密码学、数据压缩等领域都有实际应用。例如在嵌入式系统中我们经常需要检查或设置特定的位在密码学中计算汉明重量1的个数是一个基本操作。9. 个人心得与建议在解决这个问题时我有几点体会不要被题目描述迷惑看似硬件问题实则是算法题从简单方法开始暴力法虽然笨但往往是最可靠的起点善用语言特性不同语言提供的位运算工具可以简化代码注意输出格式特别是时间格式化这种细节容易出错对于刷题建议我认为这道题适合用来练习位运算基础组合问题的枚举方法边界条件处理代码的清晰性和正确性最后提醒一点在面试中遇到这类问题时一定要先和面试官确认输入输出的具体要求比如时间格式、异常处理等这能展现你的沟通能力和严谨性。