算法题day37日（补5.23日卡：贪心算法day4）

一、刷题：

1.leetcode题目 860. 柠檬水找零 - 力扣（LeetCode）（easy）：

我觉得我写的代码有点蠢

class Solution:def lemonadeChange(self, bills: List[int]) -> bool:dict_ = {5:0,10:0}if bills[0] != 5:return Falsefor i in bills:if i == 5 :dict_[i] += 1if i== 10:if dict_[5] ==0:return Falseif dict_[5] !=0:dict_[i] += 1dict_[5] -= 1if i == 20:if dict_[5] == 0:return Falseelif dict_[5]<3 and dict_[10]==0:return Falseelse:if dict_[10]>0:dict_[10] -=1 dict_[5]  -=1else:dict_[5] -= 3return True

2.leetcode 题目 406. 根据身高重建队列 - 力扣（LeetCode）(medium）

解决：

这题我没想出来，好像套路就是贪心的题目有组合的顺序的，先按照其中一个排序，再推出下一步。

class Solution:def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:people.sort(key = lambda x:(-x[0],x[1]))  ###神奇的贪心算法que = []for p in people:que.insert(p[1],p)return que

3.leetcode题目 452. 用最少数量的箭引爆气球 - 力扣（LeetCode）(medium）

解决：

注意更新箭挨得最近的爆破点

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