LeetCode 401 二进制手表 - Swift 题解

文章目录摘要描述题解答案题解代码分析为什么可以直接枚举 h 和 mnonzeroBitCount 在算什么时间字符串怎么拼示例 1 简要说明turnedOn 1示例 2turnedOn 9示例测试及结果示例 1turnedOn 1示例 2turnedOn 9以及 10示例 3turnedOn 0示例 4turnedOn 8时间复杂度空间复杂度与实际场景的结合总结摘要这道题把一块「二进制手表」抽象成 10 个二进制位上面 4 位表示小时 011下面 6 位表示分钟 059每一位亮或灭对应 0 或 1最低位在右侧和题目里的图示一致。给你整数turnedOn表示当前一共亮了几盏灯要你列出所有能表示出来的合法时间字符串。小时不能写成01:00这种带前导零的形式分钟必须是两位可以写成10:02。做法很直接枚举所有合法的小时h011和分钟m060用二进制里 1 的个数Swift 里用nonzeroBitCount判断h和m里一共亮了几位等于turnedOn就拼成h:mm加入答案。下面用 Swift 实现并说明格式化和边界。描述二进制手表顶部有 4 个 LED 表示小时011底部 6 个 LED 表示分钟059。每个 LED 表示 0 或 1最低位在右侧。给定整数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 的个数之和等于turnedOn即为一组可行解再按题目规则格式化字符串即可。题解答案classSolution401{funcreadBinaryWatch(_turnedOn:Int)-[String]{varresult:[String][]forhin0..12{formin0..60{ifh.nonzeroBitCountm.nonzeroBitCountturnedOn{letmmm10?0\(m):\(m)result.append(\(h):\(mm))}}}returnresult}}题解代码分析为什么可以直接枚举 h 和 m合法的小时只有 12 种取值011分钟只有 60 种059一共 12×60720 种组合。对每种组合手表上 10 个二进制位对应的数值就是h和m的二进制展开4 位足够表示 011最大 11 是10116 位足够表示 059最大 59 不到 64。题目里「亮着的 LED 数量」就是h的二进制里 1 的个数加上m的二进制里 1 的个数。所以不需要真的去摆弄 10 个灯的位置只要双重循环枚举(h, m)用nonzeroBitCount数 1 的个数即可。数据规模很小枚举完全够用代码也好懂。nonzeroBitCount 在算什么在 Swift 里Int的nonzeroBitCount返回该整数用二进制表示时 1 的个数也叫 popcount。例如1是1个数为 14是100个数为 111是1011个数为 3。小时h和分钟m各自独立编码到 4 位和 6 位里题目等价于popcount(h) popcount(m) turnedOn。注意我们用的是整数的完整二进制位但因为h 12、m 60高位自然是 0不会多出「虚构的灯」和题目语义一致。时间字符串怎么拼小时h是 011直接\(h)即可不会出现01这种非法形式0 就输出0。分钟必须两位若m 10前面补一个0否则用\(m)。也可以写成String(format: %d:%02d, h, m)效果等价。题目允许返回顺序任意所以不需要排序若要和官方示例逐字一致可以再对结果排序但判题一般只比较集合是否相同。示例 1 简要说明turnedOn 1恰好亮 1 盏灯要么是分钟的某一个二进制位为 1、小时全 0要么是小时某一个二进制位为 1、分钟全 0。分钟里只有一位为 1 的数是 1、2、4、8、16、32对应0:01…0:32小时里只有一位为 1 且小于 12 的数是 1、2、4、8对应1:00、2:00、4:00、8:00。共 10 个字符串与示例一致。示例 2turnedOn 9小时最多 4 位二进制里 1 的个数最多 3例如 7、11分钟在 059 里1 的个数最多 5例如 59。两者之和最大为 8不可能达到 9故答案为空数组。示例测试及结果示例 1turnedOn 1应得到 10 个时间0:01、0:02、0:04、0:08、0:16、0:32以及1:00、2:00、4:00、8:00。顺序可与题目不同集合需一致。示例 2turnedOn 9以及 10小时与分钟的二进制里 1 的个数之和最大为 8故turnedOn为 9 或 10 时都无解输出空数组。示例 3turnedOn 0只有全灭0:00即小时 0、分钟 0各 0 个 1。示例 4turnedOn 8可行组合很少需 h、m 的 popcount 之和为 8可手算或程序枚举核对例如7:597 有 3 个 159 有 5 个 1是一种。时间复杂度枚举 O(12×60)O(1) 常数级别每次nonzeroBitCount在固定字长上 O(1)。整体O(1)与 turnedOn 无关与固定上界 720 有关。空间复杂度结果数组最多存所有合法时间数量有上界远小于 720除输出外只用了常数辅助变量O(1)额外空间输出不计入则如此若计入输出则为 O(答案个数)。与实际场景的结合这类「有限状态 位计数」的模型和硬件里用若干位表示多个量、总功耗或总「选中数」有约束的场景类似例如用一组开关编码多个档位要求「恰好打开 k 个开关」时所有合法配置或在低功耗设备上用二进制位表示多个标志位统计某类组合是否合法。本题把「灯数」约束转成 popcount是常见的位运算思维训练。总结LeetCode 401 二进制手表枚举小时 011、分钟 059当h.nonzeroBitCount m.nonzeroBitCount turnedOn时将时间格式化为「小时无前导零、分钟两位补零」的字符串加入结果。实现简单、复杂度常数级注意turnedOn为 9 或 10 时无解因为 h、m 的 popcount 之和最大为 8。