leetcode 401. 二进制手表

题目描述

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

例如,上面的二进制手表读取 “3:25”。
给定一个非负整数 n 代表当前 LED 亮着的数量,返回所有可能的时间。

案例:
输入: n = 1
返回: [“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”]

注意事项:

  • 输出的顺序没有要求。
  • 小时不会以零开头,比如 “01:00” 是不允许的,应为 “1:00”。
  • 分钟必须由两位数组成,可能会以零开头,比如 “10:2” 是无效的,应为 “10:02”。

题解

前六位代表分钟,后四位代表时钟,组成十位二进制,当num=1时,共计0000000001~1000000000 10种可能,换成十进制即是1~512,因为前六位代表的分钟,所以hour小时就等于十进制数值除以64,minute分钟则是对64取模,当num=2,3,4...时,对于bits每一个值,左边依次找一个二进制位变为1,比如0000010000可以变成0000110000, 0001010000一直到1000010000,同时也要排除掉大于768和在[60,64]之间的值,因为时钟不能为12,分钟不能大于59

示例代码(go)

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
func readBinaryWatch(num int) []string {
times := []string{}
if num == 0 {
return []string{"0:00"}
}
bits := []int{1}
for i := 0; i < 9; i++ {
bits = append(bits, bits[i]*2)
}
for i := 1; i < num; i++ {
nextBits := []int{}
for _, v := range bits {
for add := 1; add <= 512; add *= 2 {
if v + add >= 768 || (v + add >= 60 && v + add < 64) {
continue
}
if add > v {
nextBits = append(nextBits, v + add)
}
}
}
bits = nextBits
}
for _, v := range bits {
hour := v / 64
minute := v % 64
times = append(times, fmt.Sprintf("%d:%02d", hour, minute))
}
return times
}