Leetcode 401:二进制手表(最详细的解法!!!)

二进制手表顶部有 4 个 LED 代表小时(0-11),底部的 6 个 LED 代表分钟(0-59)

每个 LED 代表一个 0 或 1,最低位在右侧。



例如,上面的二进制手表读取 “3:25”。

给定一个非负整数 n 代表当前 LED 亮着的数量,返回所有可能的时间。

案例:

1
2
输入: 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”。

解题思路

这个问题使用回溯法可以很快的解决,我们首先看递归的边界条件,无非是

1
if hours >= 12 or mins > 59:

然后我们结束时,添加元素的操作

1
result.append("%d:%02d"%(hours, mins))

因为总共只有10个灯,所以我们遍历的条件end=10,那么start是多少呢?start应该是上一次遍历的后一位。并且由于hoursmins的关系,所以我们要对i<4i>=4分开考虑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def readBinaryWatch(self, num):
"""
:type num: int
:rtype: List[str]
"""
result = list()
self._readBinaryWatch(num, 0, 0, 0, result)
return result

def _readBinaryWatch(self, num, hours, mins, i, result):
if hours >= 12 or mins > 59:
return

if not num:
result.append("%d:%02d"%(hours, mins))
return

for i in range(i, 10):
if i < 4:
self._readBinaryWatch(num - 1, hours | (1 << i), mins, i + 1, result)
else:
k = i - 4
self._readBinaryWatch(num - 1, hours, mins | (i << k), i + 1, result)

一个优雅的写法,意思很明确。

1
2
3
4
5
6
7
8
9
class Solution:
def readBinaryWatch(self, num):
"""
:type num: int
:rtype: List[str]
"""
return ['%d:%02d' % (h, m)
for h in range(12) for m in range(60)
if (bin(h) + bin(m)).count('1') == num]

c++中没有办法使用(bin(h) + bin(m)).count('1')的写法,所以我们自己写了一个函数

1
2
3
4
5
6
7
8
9
10
unsigned int countOnes(int num)
{
unsigned int count = 0;
while (num != 0)
{
num = num & (num - 1);
count++;
}
return count;
}

这实际上引出了一个有意思的话题,如何计算一个数的二进制有多少个1。这里面已经触及到了c++的黑魔法了,有兴趣的话,大家可以了解一下,我不多说。

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!