題目:

A binary watch has 4 LEDs on the top to represent the hours (0-11), and 6 LEDs on the bottom to represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.

Given an integer turnedOn which represents the number of LEDs that are currently on (ignoring the PM), return all possible times the watch could represent. You may return the answer in any order.

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".

binary watch是個用燈來表示時間的手錶
時的部分燈有1,2,4,8,分的部分燈有1,2,4,8,16,32
如亮時:4,分:32,16,2,1則表示現在4:51
給定一數n表示binary watch亮了n個燈,回傳一個陣列包含所有當下可能時間
特別注意若分的部分為個位數要補0,時的部分則不用,如4:01

我們以亮0燈代表的0:00,往後推斷出各種可能

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        if turnedOn==0:
            return ["0:00"]
        if turnedOn>=9:
            return []
        
        ans=[[0,0]]
        temp=[]
        t=[1,2,4,8,1,2,4,8,16,32]
        
        for i in range(turnedOn):
            
            for j in ans:
                for k in range(len(t)):
                    if k<=3: 
                        if not j[0]&t[k] and j[0]+t[k]<12 and [j[0]+t[k],j[1]] not in temp:
                            temp.append([j[0]+t[k],j[1]])
                    else:
                        if not j[1]&t[k] and j[1]+t[k]<60 and [j[0],j[1]+t[k]] not in temp:
                            temp.append([j[0],j[1]+t[k]])
            ans=temp
            temp=[]
            
        realans=[]   
        for i in ans:
            if i[1]>=10:
                realans.append(str(i[0])+":"+str(i[1]))
            else:
                realans.append(str(i[0])+":0"+str(i[1]))
                
        return realans

作法就是以亮n-1個燈的可能,去推出亮n個燈的可能
1,2,4,8......,以二進位表示為1,10,100,1000......
由此可知,燈其實是表示該分or時的二進位表示的第1,2,3.....位是否為1
透過分or時&1,2,4,8......,就能知道該燈是不是亮的(結果非0表亮)

因此我們用亮n-1個燈的可能,嘗試多亮一個燈
若此燈還沒亮(用&判斷)且不會讓時>11 or 分>59
就是其中一個亮n個燈的可能時間
我們從亮0燈一步一步推到亮n燈的可能
再將這些可能轉為題目要求格式回傳
最後執行時間81ms(faster than 7.30%)

好吧,看來效率偏差
感覺我最近用dp的時機都不太好

後來我又想到,既然燈是表示該分or時的二進位表示的第1,2,3.....位是否為1
那亮n個燈不就表示時和分的二進位表示總共有n個1

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        ans=[]

        for h in range(12):
            for m in range(60):
                if bin(h).count("1")+bin(m).count("1")==turnedOn:

                    strh=str(h)
                    strm=str(m)

                    if m<10:
                        strm="0"+strm

                    ans.append(strh+":"+strm)

        return ans

於是我考慮(0~11):(0~59)的所有可能
若該可能時和分的二進位表示總共有n個1
則將其加入ans,最後回傳ans
最後執行時間36ms(faster than 89.70%)

那我們下題見