TNotes.leetcode

Appearance

0401. 二进制手表【简单】

0401. 二进制手表【简单】 ​

1. 📝 题目描述 ​

二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。

  • 例如，下面的二进制手表读取 "4:51"。

img

给你一个整数 turnedOn，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。

小时不会以零开头：

  • 例如，"01:00" 是无效的时间，正确的写法应该是 "1:00"。

分钟必须由两位数组成，可能会以零开头：

  • 例如，"10:2" 是无效的时间，正确的写法应该是 "10:02"。

示例 1：

txt
输入：turnedOn = 1
输出：["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

示例 2：

txt
输入：turnedOn = 9
输出：[]

提示：

  • 0 <= turnedOn <= 10

2. 🎯 s.1 - 暴力解法 ​

js
/**
 * @param {number} turnedOn
 * @return {string[]}
 */
var readBinaryWatch = function (turnedOn) {
  const res = []

  // 枚举所有合法的小时和分钟
  for (let h = 0; h <= 11; h++) {
    for (let m = 0; m <= 59; m++) {
      // 小时二进制中 1 的个数
      const hOnes = h.toString(2).split('1').length - 1
      // 分钟二进制中 1 的个数
      const mOnes = m.toString(2).split('1').length - 1
      // 判断小时和分钟的二进制中 1 的个数之和是否等于 turnedOn
      if (hOnes + mOnes === turnedOn) {
        // 按照题目要求，格式化分钟为两位数
        res.push(`${h}:${m < 10 ? '0' + m : m}`)
      }
    }
  }

  return res
}
js
/**
 * @param {number} turnedOn
 * @return {string[]}
 */
var readBinaryWatch = function (turnedOn) {
  const res = []

  // 枚举所有合法的小时和分钟
  for (let h = 0; h <= 11; h++) {
    for (let m = 0; m <= 59; m++) {
      // 小时二进制中 1 的个数
      const hOnes = bitCount(h)
      // 分钟二进制中 1 的个数
      const mOnes = bitCount(m)
      // 判断小时和分钟的二进制中 1 的个数之和是否等于 turnedOn
      if (hOnes + mOnes === turnedOn) {
        // 按照题目要求，格式化分钟为两位数
        res.push(`${h}:${m < 10 ? '0' + m : m}`)
      }
    }
  }

  return res
}

function bitCount(n) {
  let count = 0
  while (n) {
    count++
    n &= n - 1 // 清除最低位的1
  }
  return count
}
  • 时间复杂度：O(1)
  • 空间复杂度：O(1)
  • js-1 直接将 n 转为字符串二进制的形式，通过切片来暴力计算 1 的数量
  • js-2 通过位运算来计算 n 对应的二进制中 1 的数量
  • 算法思路：
    • 我们可以 枚举所有合法的小时和分钟组合，并检查它们的二进制中 1 的个数之和是否等于 turnedOn。
    • 小时范围：0 ~ 11 → 枚举 h = 0 to 11
    • 分钟范围：0 ~ 59 → 枚举 m = 0 to 59
    • 对于每个 (h, m)，计算 bitCount(h) + bitCount(m) === turnedOn
    • 如果符合，格式化后加入结果数组

Discussions