Easy

题目描述

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

解题思路

这道题有两种主要的解题思路：

方法一：位运算暴力枚举 最直观的方法是枚举所有可能的时间组合，然后检查每个时间对应的二进制表示中有多少个1。小时范围是0-11（4位），分钟范围是0-59（6位）。我们可以遍历所有有效的小时和分钟组合，统计它们二进制表示中1的个数是否等于turnedOn。

方法二：回溯算法 使用回溯的方式，从10个LED位置中选择turnedOn个位置点亮，然后检查对应的时间是否有效。

推荐解法：位运算暴力枚举 考虑到数据规模较小（小时最多12种，分钟最多60种），直接暴力枚举所有可能的时间组合是最简单高效的方法。我们使用内置的位运算函数来计算二进制中1的个数，然后检查小时和分钟的1的个数之和是否等于turnedOn。

时间格式化时需要注意：小时不需要前导零，分钟需要保证两位数格式。

代码实现

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++) {
                if (__builtin_popcount(h) + __builtin_popcount(m) == turnedOn) {
                    result.push_back(to_string(h) + ":" + (m < 10 ? "0" : "") + to_string(m));
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        result = []
        
        for h in range(12):
            for m in range(60):
                if bin(h).count('1') + bin(m).count('1') == turnedOn:
                    result.append(f"{h}:{m:02d}")
        
        return result

public class Solution {
    public IList<string> ReadBinaryWatch(int turnedOn) {
        IList<string> result = new List<string>();
        
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                if (CountBits(h) + CountBits(m) == turnedOn) {
                    result.Add($"{h}:{m:D2}");
                }
            }
        }
        
        return result;
    }
    
    private int CountBits(int n) {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
}

/**
 * @param {number} turnedOn
 * @return {string[]}
 */
var readBinaryWatch = function(turnedOn) {
    const result = [];
    
    for (let h = 0; h < 12; h++) {
        for (let m = 0; m < 60; m++) {
            const hourBits = h.toString(2).split('0').join('').length;
            const minuteBits = m.toString(2).split('0').join('').length;
            
            if (hourBits + minuteBits === turnedOn) {
                result.push(`${h}:${m.toString().padStart(2, '0')}`);
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(1)
空间复杂度O(1)

说明：虽然有双重循环，但循环次数是固定的（12 × 60 = 720），属于常数级别。位运算计算1的个数的时间复杂度也是常数级别。

相关题目