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],结果可以按任意顺序返回;不合法的小时或分钟组合不能出现在答案中。

自建示例

没有灯亮起:

输入:turnedOn = 0
输出:["0:00"]
解释:所有小时灯和分钟灯都熄灭时,唯一能够表示的合法时间是 0:00。

亮灯数超过任何合法时间所需数量:

输入:turnedOn = 9
输出:[]
解释:合法小时最多只能同时点亮 3 个小时灯,合法分钟最多只能同时点亮 5 个分钟灯,因此不存在恰好点亮 9 个灯的合法时间。

直接枚举有限的合法时间

小时只有 0..11 共 12 种,分钟只有 0..59 共 60 种,总共 720 个候选。对每个候选分别统计小时和分钟的二进制置位数,二者之和等于 turnedOn 时才加入答案。枚举比构造灯的组合更直接,因为它天然排除了小时超过 11、分钟超过 59 的编码。

格式化时小时直接转为十进制,分钟不足两位就在前面补一个 0;亮灯数为 0 或超过可用灯数的边界都由同一套枚举自然处理。

C++ 实现

class Solution {
public:
    std::vector<std::string> readBinaryWatch(int turnedOn) {
        std::vector<std::string> 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)``(不计返回结果)。