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

【代码随想录训练营】【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]] += 1if bills[i] == 5:continueelif bills[i] == 10:money_dict[5] -= 1if money_dict[5] < 0:return Falseelse:if money_dict[10] > 0 and money_dict[5] > 0:money_dict[10] -= 1money_dict[5] -= 1elif money_dict[5] > 2:money_dict[5] -= 3else: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 - 1sum_, i = 0, 0for j in range(n):sum_ += nums[j]while sum_ >= target:result = min(result, j - i + 1)sum_ -= nums[i]i += 1if result == 2**31 -1:return 0else:return result

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

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

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