力扣刷题 day49：10

力扣刷题 day49：10"/>

力扣刷题 day49：10

1.二进制手表

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

例如，下面的二进制手表读取 "4:51" 。

给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。

小时不会以零开头：

例如，"01:00" 是无效的时间，正确的写法应该是 "1:00" 。
分钟必须由两位数组成，可能会以零开头：

例如，"10:2" 是无效的时间，正确的写法应该是 "10:02" 。

方法一：直接遍历

#方法一：直接遍历
def readBinaryWatch(turnedOn):def count1(n):res=0while n:res+=n&1n>>=1return res  #计算1的个数ans=[]for i in range(12):for j in range(60):if count1(i)+count1(j)==turnedOn: #看看1的个数等不等于亮灯的个数if j<10:ans.append(str(i)+":0"+str(j)) #特殊补0else:ans.append(str(i)+":"+str(j))return ans 

2.多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

方法一：排序 

#方法一：排序
def majorityElement(nums):nums=sorted(nums) #先排序return nums[len(nums)//2]  #中间元素一定是多数元素

方法二：摩尔投票法 

#方法二：摩尔投票法
def majorityElement(nums):count=0target=nums[0] #先假定目标值为这个for i in range(len(nums)):if count==0:target=nums[i]  #转换目标值，因为当前目标值已经和非目标值抵消了，所以重新开始继续找if target==nums[i]:count+=1 #如果值相等，说明是同类，投票数目加一else:count-=1 #不是同类，投票数目-1return target