0401. Binary Watch
==================
题目信息
--------
:题号: 0401
:难度: Easy
:主题: 二进制手表、合法时间、亮灯计数、结果枚举
:原题: `LeetCode 0401 `_
:重点: 4 个小时灯与 6 个分钟灯分别计数、恰好点亮指定数量、分钟固定两位、结果顺序不限
题目重述
--------
二进制手表使用 4 个 LED 表示小时、6 个 LED 表示分钟。给定整数 ``turnedOn``,返回所有恰好有 ``turnedOn`` 个 LED 亮起时能够表示的合法时间。
小时必须位于 ``0..11``,分钟必须位于 ``0..59``。输出格式为 ``"h:mm"``:小时不能补前导零,分钟必须恰好两位。``turnedOn`` 位于 ``[0, 10]``,结果可以按任意顺序返回;不合法的小时或分钟组合不能出现在答案中。
自建示例
--------
没有灯亮起:
.. code-block:: text
输入:turnedOn = 0
输出:["0:00"]
解释:所有小时灯和分钟灯都熄灭时,唯一能够表示的合法时间是 0:00。
亮灯数超过任何合法时间所需数量:
.. code-block:: text
输入:turnedOn = 9
输出:[]
解释:合法小时最多只能同时点亮 3 个小时灯,合法分钟最多只能同时点亮 5 个分钟灯,因此不存在恰好点亮 9 个灯的合法时间。
直接枚举有限的合法时间
------------------------
小时只有 ``0..11`` 共 12 种,分钟只有 ``0..59`` 共 60 种,总共 720 个候选。对每个候选分别统计小时和分钟的二进制置位数,二者之和等于 ``turnedOn`` 时才加入答案。枚举比构造灯的组合更直接,因为它天然排除了小时超过 11、分钟超过 59 的编码。
格式化时小时直接转为十进制,分钟不足两位就在前面补一个 ``0``;亮灯数为 0 或超过可用灯数的边界都由同一套枚举自然处理。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
std::vector readBinaryWatch(int turnedOn) {
std::vector result;
for (int hour = 0; hour < 12; ++hour) {
for (int minute = 0; minute < 60; ++minute) {
if (__builtin_popcount(hour)
+ __builtin_popcount(minute) != turnedOn) {
continue;
}
std::string time = std::to_string(hour) + ":";
if (minute < 10) time += "0";
time += std::to_string(minute);
result.push_back(time);
}
}
return result;
}
};
代码分析
--------
小时的 4 位和分钟的 6 位互不混淆,置位数相加正好对应 LED 总数;输出格式只在分钟部分补零,不会把小时写成 ``00``。候选数固定为 720,时间复杂度为 ``O(12 * 60)``,额外空间为 ``O(1)``(不计返回结果)。