算法题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 False
        for i in bills:
            if i == 5 :
                dict_[i] += 1
            if i== 10:
                if dict_[5] ==0:
                    return False
                if dict_[5] !=0:
                    dict_[i] += 1
                    dict_[5] -= 1
            if i == 20:
                if dict_[5] == 0:
                    return False
                elif dict_[5]<3 and dict_[10]==0:
                    return False
                else:
                    if dict_[10]>0:
                        dict_[10] -=1 
                        dict_[5]  -=1
                    else:
                        dict_[5] -= 3
        return 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 = 1
        for i in range(1,len(points)):
            if points[i][0]>points[i-1][1]:
                ans +=1
            else:
                points[i][1] = min(points[i-1][1],points[i][1])
        return ans