LeetCode 第401题：二进制手表

📖 文章摘要

本文详细解析LeetCode第401题“二进制手表”，这是一道位运算和回溯的组合问题。文章提供了完整的解题思路，包含C#、Python、C++三种语言实现，配有详细的分析和性能对比。适合想要学习位运算和回溯算法的读者。

核心知识点： 位运算、回溯算法、时间表示
难度等级： 简单
推荐人群： 对位运算感兴趣的初学者

题目描述

二进制手表顶部有 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

解题思路

这道题可以使用以下几种方法来解决：

枚举法
- 遍历所有可能的小时（0-11）和分钟（0-59）组合
- 计算每个时间的二进制中1的个数
- 如果1的个数等于turnedOn，则是有效答案
回溯法
- 分别处理小时和分钟的LED
- 通过回溯来尝试不同的LED组合
- 确保小时在0-11范围内，分钟在0-59范围内
位运算法
- 使用位运算来计算1的个数
- 通过位掩码生成所有可能的组合
- 快速筛选出符合条件的时间

本文将主要介绍位运算法，因为它最为高效。

图解思路

算法步骤分析表

步骤	操作	状态	说明
初始状态	-	LED全灭	初始状态所有LED都是0
第一步	遍历小时	0-11	检查每个小时值中1的个数
第二步	遍历分钟	0-59	检查每个分钟值中1的个数
第三步	组合时间	格式化	将有效的小时和分钟组合成时间字符串

状态/情况分析表

情况	输入	输出	说明
基本情况	turnedOn = 1	[“0:01”, …]	只有一个LED亮起的所有可能时间
特殊情况	turnedOn = 0	[“0:00”]	所有LED都不亮的情况
无效情况	turnedOn > 8	[]	LED数量超过最大可能值

代码实现

C# 实现

public class Solution {
    public IList<string> ReadBinaryWatch(int turnedOn) {
        var result = new List<string>();
        
        // 遍历所有可能的小时和分钟组合
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                // 计算小时和分钟中1的个数
                if (CountBits(h) + CountBits(m) == turnedOn) {
                    // 格式化时间字符串
                    result.Add($"{h}:{m:D2}");
                }
            }
        }
        
        return result;
    }
    
    // 计算二进制中1的个数
    private int CountBits(int n) {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
}

Python 实现

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        def count_bits(n: int) -> int:
            return bin(n).count('1')
        
        result = []
        # 遍历所有可能的小时和分钟组合
        for h in range(12):
            for m in range(60):
                # 如果1的个数等于turnedOn，添加到结果中
                if count_bits(h) + count_bits(m) == turnedOn:
                    result.append(f"{h}:{m:02d}")
        
        return result

C++ 实现

class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> result;
        
        // 遍历所有可能的小时和分钟组合
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                // 如果1的个数等于turnedOn，添加到结果中
                if (__builtin_popcount(h) + __builtin_popcount(m) == turnedOn) {
                    result.push_back(
                        to_string(h) + ":" + 
                        (m < 10 ? "0" : "") + to_string(m)
                    );
                }
            }
        }
        
        return result;
    }
};

执行结果

C# 实现

执行用时：108 ms
内存消耗：42.1 MB

Python 实现

执行用时：36 ms
内存消耗：15.1 MB

C++ 实现

执行用时：0 ms
内存消耗：6.3 MB

性能对比

语言	执行用时	内存消耗	特点
C#	108 ms	42.1 MB	代码简洁，但性能较差
Python	36 ms	15.1 MB	实现简单，性能中等
C++	0 ms	6.3 MB	性能最优，内存占用最小

代码亮点

🎯 使用位运算高效计算二进制中1的个数
💡 利用语言内置的格式化功能处理时间字符串
🔍 合理处理分钟的前导零
🎨 代码结构清晰，易于理解和维护

常见错误分析

🚫 忽略分钟需要补零的情况
🚫 没有正确处理小时和分钟的范围限制
🚫 使用低效的字符串拼接方法
🚫 重复计算相同数字的二进制1的个数

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
枚举法	O(1)	O(1)	实现简单，直观	需要遍历所有可能时间
回溯法	O(C(10,n))	O(n)	避免无效组合	实现复杂
位运算法	O(1)	O(1)	性能最优	需要理解位运算

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第401题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

图解思路

算法步骤分析表

状态/情况分析表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流