【代碼隨想錄訓練營】【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