問題描述
GA binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).
Each LED represents a zero or one, with the least significant bit on the right.
示例圖
For example, the above binary watch reads "3:25".
Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.
Example:
Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
Note:
The order of output does not matter.
The hour must not contain a leading zero, for example "01:00" is not valid, it should be "1:00".
The minute must be consist of two digits and may contain a leading zero, for example "10:2" is not valid, it should be "10:02".
補(bǔ)充說明：
這個(gè)題目的大體意思是津肛，有這么一個(gè)LED燈表示的表（如圖示）药版，上面4個(gè)LED表示時(shí)鐘，下面6個(gè)LED表示分鐘。燈亮表示對應(yīng)的bit位為1每窖。這些燈代表的bit位組合成的數(shù)字就是對應(yīng)當(dāng)前時(shí)間時(shí)鐘數(shù)和分鐘數(shù)（圖上表示3:25）。現(xiàn)在需要你寫一段代碼藕坯，輸入要亮燈的個(gè)數(shù)（不分時(shí)鐘還是分鐘）伍纫，對應(yīng)輸出這些個(gè)數(shù)的燈能組成的所有時(shí)間。
這里還有一些小點(diǎn)需要注意：
- 輸出的順序無關(guān)緊要钳恕。
- 小時(shí)不能包含前導(dǎo)0别伏，例如“01:00”無效，應(yīng)為“1:00”忧额。
- 分鐘必須由兩位數(shù)字組成厘肮，并且可能包含前0，例如“10：2”無效睦番，應(yīng)為“10:02”类茂。
方案分析
- 這個(gè)問題都能一下子想到它的最簡單解，就是遍歷時(shí)鐘和分鐘數(shù)的每一個(gè)時(shí)間段托嚣，如果這兩個(gè)數(shù)字里面包含的數(shù)字‘1’的
個(gè)數(shù)的總和為輸入的數(shù)字巩检。這顯然是一個(gè)愚蠢的做法，因?yàn)檫@個(gè)循環(huán)會(huì)執(zhí)行12 × 60次示启。
python實(shí)現(xiàn)
class Solution(object):
def readBinaryWatch(self, num):
return ['%d:%02d' % (h, m)
for h in range(12) for m in range(60)
if (bin(h) + bin(m)).count('1') == num]
方案分析2
- 上面的方式是最為傳統(tǒng)的思想兢哭，那么有什么辦法能提高一點(diǎn)執(zhí)行速度么，于是找到了下面一種方法丑搔。這種方法采用了空間換時(shí)間的方式厦瓢，先將小時(shí)和分鐘的二進(jìn)制表示中1的個(gè)數(shù)hash表保存起來（相當(dāng)于自己實(shí)現(xiàn)了一個(gè)上面的
count(str)方法）提揍。這里比上面效率高的地方在于，它并不會(huì)執(zhí)行12 × 60次煮仇，而是先保障時(shí)鐘的循環(huán)次數(shù)的情況下劳跃，內(nèi)部(循環(huán)num - 小時(shí)所用１的位數(shù))次。
python實(shí)現(xiàn)2
class Solution(object):
# Binary Watch
def readBinaryWatch(self, num):
"""
:type num: int
:rtype: List[str]
"""
hourMap = {i: self.countOfBits(i) for i in range(12)}
minutesMap = {i: self.countOfBits(i) for i in range(60)}
res = []
for hour in filter(lambda x: hourMap[x] <= num, range(12)):
res += ["%s" % hour + ":" + ("%s" % minute).zfill(2) for minute in filter(lambda x: minutesMap[x] == num - hourMap[hour], range(60))]
return res
def countOfBits(self, num):
counter = 0
while num:
counter += 1
num &= num - 1
return counter
方案分析3
- 繞過上面兩種思路浙垫，我們再想想還有其他方式嗎刨仑？這里一共有10個(gè)LED，如果我們不關(guān)注它表示的是否是小時(shí)位還是分鐘位夹姥，那么這個(gè)問題是不是就變?yōu)榱俗屩付▊€(gè)數(shù)的位置的燈亮起或者熄滅的排列組合問題了杉武。
- 這里除了排列組合這個(gè)問題，還需要注意的是辙售，并不是所有的組合都對應(yīng)存在的時(shí)間轻抱，可能會(huì)出現(xiàn)不合理的時(shí)間。比如很明顯10個(gè)LED全部亮起就不是一個(gè)合理的時(shí)間旦部。
python實(shí)現(xiàn)3
class Solution(object):
def readBinaryWatch(self, num):
"""
:type num: int
:rtype: List[str]
"""
res = []
if num > 10 or num < 0:
return res
for comb in itertools.combinations(range(10), num):
h = int("".join(['1' if i in comb
else '0'
for i in range(4)]), 2)
m = int("".join(['1' if i in comb
else '0'
for i in range(4, 10)]), 2)
if h < 12 and m < 60:
res.append(str(h) + ":" + str(m).zfill(2))
return res
