leetcode with python:401. Binary Watch

题目:

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%)

那我们下题见