【代码随想录训练营】【Day 37】【贪心-4】| Leetcode 840, 406, 452

需强化知识点

python list sort的高阶用法，两个key，另一种逆序写法
python list insert的用法

题目

860. 柠檬水找零

思路：注意 20 块找零，可以找3张5块
升级版：可以直接用变量记录次数，five，ten

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        money_dict = {5:0, 10:0, 20:0}

        for i in range(len(bills)):
            money_dict[bills[i]] += 1
            if bills[i] == 5:
                continue
            elif bills[i] == 10:
                money_dict[5] -= 1
                if money_dict[5] < 0:
                    return False
            else:
                if money_dict[10] > 0 and money_dict[5] > 0:
                    money_dict[10] -= 1
                    money_dict[5] -= 1
                elif money_dict[5] > 2:
                    money_dict[5] -= 3
                else:
                    return False        
        return True

406. 根据身高重建队列

题目含义：原先的people是打乱顺序，现在要重新排序得到queue
思路：首先对people进行排序，先按照身高降序排序，身高相同时根据 ki 进行升序排列，这里key的传参很妙；然后构建新的队列，插入的思想，以kj为依据进行插入，实现同样身高的，ki小的排在前面
insert（索引值，插入的元素）

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        result = 2 ** 31 - 1
        sum_, i = 0, 0

        for j in range(n):
            sum_ += nums[j]
            while sum_ >= target:
                result = min(result, j - i + 1)
                sum_ -= nums[i]
                i += 1
        if result == 2**31 -1:
            return 0
        else:
            return result

452. 用最少数量的箭引爆气球

思路：重叠的气球都一起射 -> 记录和更新重叠区间。point根据初始位置进行排序，如果新位置不在重叠区间内，则增加次数，更新重叠区间

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key = lambda x: x[0])
        times = 1
        sl, sr = points[0][0], points[0][1]
        for i in range(1, len(points)):
            if points[i][0] > sr:
                times += 1
                sl, sr = points[i][0], points[i][1]
            sl, sr = max(sl, points[i][0]), min(sr, points[i][1])
        return times