力扣刷题 day49：10-19

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=0
        while n:
            res+=n&1
            n>>=1
        return 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)) #特殊补0
                else:
                    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=0
    target=nums[0] #先假定目标值为这个
    for i in range(len(nums)):
        if count==0:
            target=nums[i]  #转换目标值，因为当前目标值已经和非目标值抵消了，所以重新开始继续找
        if target==nums[i]:
            count+=1 #如果值相等，说明是同类，投票数目加一
        else:
            count-=1 #不是同类，投票数目-1
        
    return target