401. 二进制手表

🟢   🔖  位运算 回溯  🔗 力扣 LeetCode

题目

A binary watch has 4 LEDs on the top to represent the hours (0-11), and 6 LEDs on the bottom to represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.

• For example, the below binary watch reads "4:51".

Given an integer turnedOn which represents the number of LEDs that are currently on (ignoring the PM), return all possible times the watch could represent. You may return the answer in any order.

The hour must not contain a leading zero.

• For example, "01:00" is not valid. It should be "1:00".

The minute must consist of two digits and may contain a leading zero.

• For example, "10:2" is not valid. It should be "10:02".

Example 1:

Input: turnedOn = 1

Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

Example 2:

Input: turnedOn = 9

Output: []

Constraints:

• 0 <= turnedOn <= 10

题目大意

二进制手表顶部有 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]
   • 分钟范围：[0, 59]

2. 统计 LED 亮的数量：

   • 使用 countBits 函数来计算数字的二进制表示中 1 的个数。
   • countBits 的实现利用位运算：
     • num & 1 检查当前最低位是否为 1。
     • num >>= 1 将数字右移一位，继续检查下一位。

3. 筛选符合条件的时间：

   • 如果当前小时和分钟的 1 的个数之和等于 turnedOn，则将其格式化，保证分钟部分始终为两位数（例如："01", "02"），并加入结果。

复杂度分析

• 时间复杂度：O(720)， 遍历所有小时和分钟的组合：12 * 60 = 720，即常数级复杂度。
• 空间复杂度：O(720)，结果集 res 的空间复杂度取决于符合条件的时间组合，最坏情况下O(720)。

代码

/**
 * @param {number} turnedOn
 * @return {string[]}
 */
var readBinaryWatch = function (turnedOn) {
	// 统计数字的二进制表示中 1 的个数
	const countBit = (num) => {
		let count = 0;
		while (num > 0) {
			count += num & 1; // 检查最低位是否为 1
			num >>= 1; // 右移一位
		}
		return count;
	};

	let res = [];

	// 遍历所有小时和分钟的组合
	for (let hour = 0; hour < 12; hour++) {
		for (let minute = 0; minute < 60; minute++) {
			// 统计当前小时和分钟的亮灯数量
			if (countBit(hour) + countBit(minute) == turnedOn) {
				// 如果亮灯数量等于 turnedOn，则将该时间加入结果
				res.push(`${hour}:${minute < 10 ? '0' : ''}${minute}`);
			}
		}
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
17	电话号码的字母组合	[✓]	哈希表 字符串 回溯	🟠	🀄️ 🔗
191	位1的个数	[✓]	位运算 分治	🟢	🀄️ 🔗