代码随想录算法训练营第30天—贪心算法04 | ● 860.柠檬水找零 ● *406.根据身高重建队列 ● *452. 用最少数量的箭引爆气球

本文主要是介绍代码随想录算法训练营第30天—贪心算法04 | ● 860.柠檬水找零 ● *406.根据身高重建队列 ● *452. 用最少数量的箭引爆气球，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

860.柠檬水找零

https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html

考点
- 贪心算法
我的思路
- 三层逻辑判断，分别判断收5块、10块和20块的情况，并用一个数组记录手头有的零钱
视频讲解关键点总结
- 用数组记录手头有的零钱会导致取钱时时间复杂度高，因此直接用整型变量记录5块和10块的数量即可
我的思路的问题
- 时间复杂度高
代码书写问题
- 无
可执行代码

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

*406.根据身高重建队列

https://programmercarl.com/0406.%E6%A0%B9%E6%8D%AE%E8%BA%AB%E9%AB%98%E9%87%8D%E5%BB%BA%E9%98%9F%E5%88%97.html

考点
- 贪心算法
- 分而治之
我的思路
- 无思路
视频讲解关键点总结
- 分而治之，先按照身高倒序排列（由高到低）
- 再按照前面有几个比自己高的数将元素插入对应位置
我的思路的问题
- 无思路
代码书写问题
- 可以利用lambda语法进行排序
可执行代码

class Solution:def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:people.sort(key=lambda x: (-x[0], x[1]))result = []for data in people:result.insert(data[1], data)return result

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

https://programmercarl.com/0452.%E7%94%A8%E6%9C%80%E5%B0%91%E6%95%B0%E9%87%8F%E7%9A%84%E7%AE%AD%E5%BC%95%E7%88%86%E6%B0%94%E7%90%83.html

考点
- 贪心算法
- 重叠区间
我的思路
- 先按照左坐标对气球排序
- 之后判断重叠情况，即下一气球的左坐标是否小于等于当前气球右坐标，小于时重叠，重叠则将下一气球的右坐标更新为交集的右坐标
- 在此过程中对箭进行计数
视频讲解关键点总结
- 我的思路中有两个细节问题，一是箭的计数，二是重叠区间的更新；大致思路是没问题的
- 一，箭的计数，合理的计数方式是在初始化时就默认有一支箭，之后如果后面的气球和当前气球有重叠，箭的数量不增加；无重叠，箭的数量就增加
- 二，重叠区间的更新，主要是后一气球的右坐标应以当前气球和后一气球右坐标中较小者为参考，而不是直接以当前气球右坐标为参考，因为其可能反而比后一气球的右坐标大
我的思路的问题
- 见上
代码书写问题
- 无
可执行代码

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