一些有趣的题目

NO.229 求众数II(此题不一定存在符合条件的元素，因此还需检验）
法一：直接统计，如果大于1/3，加入到答案里面，缺点是不满足空间复杂度为O(1)
def majorityElement(self, nums: List[int]) -> List[int]:
        ans = []
        counter = Counter(nums)
        for item in counter.keys():
            if counter[item] > len(nums) // 3:
                ans.append(item)
        return ans
法二：摩尔投票法
NO.229 求众数II
法一：直接统计，如果大于1/3，加入到答案里面，缺点是不满足空间复杂度为O(1)
def majorityElement(self, nums: List[int]) -> List[int]:
        ans = []
        counter = Counter(nums)
        for item in counter.keys():
            if counter[item] > len(nums) // 3:
                ans.append(item)
        return ans
法二：摩尔投票法
def majorityElement(self, nums: List[int]) -> List[int]:
        count1 = count2 = 0
        n1 = n2 = None
        ans = []
        for num in nums:#先找到最多的两个数,分别是n1和n2
            if num == n1:#累加次数
                count1 += 1
            elif num == n2:
                count2 += 1
            elif count1 == 0:#不够抵消，换个数
                n1 = num
                count1 += 1
            elif count2 == 0:
                n2 = num
                count2 += 1
            else:#抵消
                count1 -= 1
                count2 -= 1
        
        count3 = count4 = 0
        for num in nums:#统计最多的两个数的数量
            if num == n1:
                count3 += 1
            if num == n2:
                count4 += 1
        if count3 > len(nums)//3:#判断两个数是否大于1/3
            ans.append(n1)
        if count4 > len(nums)//3:
            ans.append(n2)
        return ans

NO.169 多数元素（题目说一定存在符合条件的元素，可以不检查）
法一：哈希表
max(iterable, *[, key, default]):去传入可迭代对象中最大值。数值型参数，取值大的；字符型参数，取字母靠后的；还可以用key指定一个函数指定获取最大值的方法。default方法用来指定最大值不存在时返回的默认值。这两个参数都是可选的
max(count.keys(), key = count.get):对count.keys的键进行排序，排序是按照get方法得到的值的大小，选最大的输出。
def majorityElement(self, nums: List[int]) -> int:
        counter = Counter(nums)
        return max(counter.keys(), key = counter.get)
法二：排序法
(n//2)处的元素是众数
def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]
法三：摩尔投票法
def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None
        for num in nums:
            if count == 0:#不够抵消时换一个
                candidate = num
            if num == candidate:#累积一个
                count += 1
            else:#抵消一个
                count -= 1
        return candidate

NO.84 柱状图中最大的矩形
在一维数组中对每一个数找到第一个比自己小的元素（这是典型的单调栈应用场景）
单调栈：单调递增/减的序列
单调栈思路：求每条柱子可以向左右延伸的长度（得到宽度），然后乘以柱子高度，得到面积
寻找柱子左/右边首个严格小于height[i]的柱子，维护一个单调递增栈（栈底——>栈顶），每当遇到新加入的元素<栈顶便可确定柱子右边界，
左边界就是栈顶柱子下面的柱子
本题引入了哨兵，在前后多加了一个高度为0的柱子，避免每次判断边界条件。
def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights) + 2 #加了两个哨兵
        new_heights = [0] * n 
        for i in range(1, n-1):#将新数组中的高度置为原高度，注意下标往后挪了一个
            new_heights[i] = heights[i-1]
        stack = []#单调递增栈
        ans = 0
        for i in range(n):#遍历新数组
            while stack and new_heights[i] < new_heights[stack[-1]]:#栈不为空且当前柱子<栈顶柱子
                pop_index = stack.pop()#右边界为索引为i的柱子（不含），左边界为栈顶元素下面的索引
                w = i - stack[-1] - 1
                h = new_heights[pop_index]#栈顶元素对应高度是矩形高度
                ans = max(ans, w*h)
            stack.append(i)#当前索引入栈
        return ans

NO.1185 一周中的第几天
法一：选基准值
def dayOfTheWeek(self, day: int, month: int, year: int) -> str:
        #1970年12月31日是周四，以此为基准计算天数差值
        week = ['Thursday','Friday','Saturday','Sunday','Monday','Tuesday','Wednesday']#星期列表
        months = [31,28,31,30,31,30,31,31,30,31,30]#每月天数，12月可以不需要，因为最后一个
        days = 0
        days += 365*(year-1971) + (year-1969) // 4 #今年之前的天数，减去1969是因为1972是闰年，但这个闰会加在月份上，往后的闰年则多一天
        for i in range(month - 1): #加上今年本月之前的天数
            days += months[i]
        if (year % 400 == 0 or (year % 4 == 0 and year % 100 != 0)) and month >= 3:#如果闰年3月以后，加一天
            days += 1
        days += day #加上本月天数
        return week[days % 7] #取余，返回值
法二：直接调库
datetime.date表示日月年
datetime.time表示小时、分钟、秒、毫秒
datetime.datetime覆盖日期和时间两类
datetime.timedelta:时间间隔
datetime.tzinfo:时区有关
datetime.datime(year, month, day)获取当前的年月日，再用strftime()格式化控制符
strftime("%A")星期，（“%a")星期缩写
def dayOfTheWeek(self, day: int, month: int, year: int) -> str:
        return datetime.datetime(year, month, day).strftime("%A")
法三：蔡勒公式（只适用于1582年格里高利历改革之后的年份）
w = ((c//4) - 2c  + y + (y//4) + (13(m+1)//5) + d - 1)mod 7
w:星期，从Sunday开始，且只能从星期天开始
c:年份前两位
y:年份后两位
m:月，范围是3——14，某年的1、2月要看成上一年的13、14月
d:日
def dayOfTheWeek(self, day: int, month: int, year: int) -> str:
        week = ['Sunday','Monday','Tuesday','Wednesday','Thursday','Friday','Saturday']
        if month <= 2: #月份要先处理，年份可能会减，会影响c和y的值
            month += 12
            year -= 1
        c = year // 100
        y = year % 100
        w = (c // 4  - 2*c + y + y//4 + 13*(month + 1) // 5 + day - 1) % 7 #蔡勒公式代入求值
        return week[w]

NO.365 水壶问题
法一：
裴蜀（贝祖）定理：对于两个整数a、b，它们的最大公约数d可以表示成a和b的线性组合。即一定存在x和y，使得ax+by = d
ax+by=z有解要求z是x,y的最大公约数的倍数
def canMeasureWater(self, x: int, y: int, target: int) -> bool:
        if x + y < target:#小于不行
            return False
        if x + y == target or x == target or y == target:
            return True
        return target % math.gcd(x, y) == 0 #裴蜀定理，求x,y的最大公约数，只要target是它的倍数就可以

法二：BFS广度优先
deque():双端队列,将数据插入指定位置,appendleft(item)将数据添加在队列的头部,pop()是从队尾弹出元素并作为返回值
def canMeasureWater(self, x: int, y: int, target: int) -> bool:
        queue = deque([(0,0)])#外括号是deque()方法，[]是因为队列的存储结构，内部()是元组存储每组水壶情况
        visited = set([(0,0)])
        while queue:
            cur_x, cur_y = queue.pop()#当前水量，分别是元组的第一个和第二个值，从队尾弹出
            if target in [cur_x, cur_y, cur_x + cur_y]:#只要target出现在当前水量的组合里，则成功
                return True
            for item in [
                (x, cur_y), (cur_x, y),#壶分别加满水
                (0, cur_y), (cur_x, 0),#壶分别倒空水
                (cur_x + cur_y - y, y) if cur_x + cur_y >= y else (0, cur_x + cur_y),#倒满y水壶：一种是加满，一种是加不满
                (x, cur_x + cur_y - x) if cur_x + cur_y >= x else (cur_x + cur_y, 0)]:#倒满x水壶：一种是加满，一种加不满
                if item not in visited:#只要这些情况没有遇到过
                    queue.appendleft(item)#从对头加入队列里，此处一定要从对头加，否则用deque没有意义，且会超时
                    visited.add(item)#添加对访问名单里
        return False

NO.458 可怜的小猪
法一：数学方法
可以喝水的次数 = minutesToTest / minutesToDie
包含的信息量 = 喝水次数 + 1
每只小猪为一个维度，共有信息量^猪的次方个点，每个点确定一个位数。
def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
        count = 0
        while (minutesToTest // minutesToDie + 1) ** count < buckets:
            count += 1
        return count
这个代码思路还是数学方法，但是少了取对数的误差，更准确。