每天进步一点点🤏

二进制手表

  • 1446 字

二进制手表

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
二进制手表顶部有 4 个 LED 代表 小时（0-11）[1,2,4,8],底部的 6 个 LED 代表 分钟（0-59）[1,2,4,8,16,32],每个 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
输出：[]

解法

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
36
37
38
39
40
思路:
每一个亮起的灯代表一个二进制的1,比如1表示0001,2表示0010,4表示0100,每个数字都代表范围内的1
亮起几个灯就表示有几个1,所以只需要遍历0-11小时和0-60分钟,将二进制1的数量相加看是否等于输入的数量

代码:

// 返回数字的二进制有几个1
private function toBit($i)
{
    $num = 0;
    while ($i) {
        $num += $i % 2 === 1 ? 1 : 0;
        $i   = intdiv($i, 2);
    }

    return $num;
}

/**
 * @param Integer $turnedOn
 *
 * @return String[]
 */
function readBinaryWatch($turnedOn)
{
    $list = [];
    for ($i = 0; $i < 12; $i++) {
        for ($j = 0; $j < 60; $j++) {
            // 枚举每个时分,led等亮起的数量=时分二进制中1的数量
            if ($this->toBit($i) + $this->toBit($j) === $turnedOn) {
                $str = $i . ':';
                $str .= $j < 10 ? '0' . $j : $j;

                $list[] = $str;
            }
        }
    }

    return $list;
}