「每日LeetCode」2022年1月26日

本文最后更新于：2023年3月19日 晚上

  1. 二进制手表

401. 二进制手表

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

  • 例如，下面的二进制手表读取 “3:25” 。

（图源：WikiMedia - Binary clock samui moon.jpg_ ，许可协议：Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0) ）_
给你一个整数 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
 * @lc app=leetcode.cn id=401 lang=javascript
 *
 * [401] 二进制手表
 */

// @lc code=start
/**
 * @param {number} turnedOn
 * @return {string[]}
 */
var readBinaryWatch = function (turnedOn) {
  const timeArr = [],
    temp = new Array(10).fill(0);
  const generate = (index, count) => {
    if (count === 0) {
      timeArr.push(temp.slice().join(""));
      return;
    }
    for (let i = index; i < 10; i++) {
      temp[i] = 1;
      generate(i + 1, count - 1);
      temp[i] = 0;
    }
  };
  generate(0, turnedOn);
  const res = [];
  for (const str of timeArr) {
    const hour = parseInt(str.slice(0, 4), 2),
      minute = parseInt(str.slice(4), 2);
    if (hour > 11 || minute > 59) continue;
    res.push(`${hour}:${(minute + "").padStart(2, 0)}`);
  }
  return res;
};