算法记录 | Day35 贪心算法

860.柠檬水找零

思路：

只需要维护三种金额的数量，5，10和20。

有如下三种情况：

• 情况一：账单是5，直接收下。
• 情况二：账单是10，消耗一个5，增加一个10
• 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5

账单是20的情况，优先消耗一个10和一个5

因为美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能！

所以局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。

class Solution:def lemonadeChange(self, bills: List[int]) -> bool:five = 0 ten = 0 twenty = 0for bill in bills:if bill == 5: five += 1if bill == 10: if five < 0: return Falseten += 1five -= 1if bill == 20:if ten > 0 and five > 0:twenty += 1ten -= 1five -=1elif five >= 3:twenty += 1five -= 3else:return Falsereturn True

406.根据身高重建队列

思路：

1.可以先确定身高维度。将数组按身高从高到低进行排序，身高相同的则按照 k值升序排列。这样排序之后可以确定目前对于第 j 个人来说，前面的 j - 1 个人肯定比他都高。

2.建立一个包含 n 个位置的空队列 queue，按照上边排好的顺序遍历，依次将其插入到第 kj位置上。最后返回新的队列。

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

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

思路：

按开始坐标升序排序需要考虑一种情况：有交集关系的区间中，有的区间结束位置比较早。比如 [0, 6] [1, 2] [4, 5]

，按照开始坐标升序排序的话，如下：

[0 . . . . . 6][1 2][4,5]

第一箭的位置需要进行迭代判断，取区间 [0, 6] [1, 2]中结束位置最小的位置，即arrow_pos = min(points[i][1], arrow_pos)，然后再判断接下来的区间是否能够引爆。

而按照结束坐标排序的话，箭的位置一开始就确定了，不需要再改变和判断箭的位置，直接判断区间即可。

按开始位置排序

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

按结束位置排序

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