本文主要是介绍算法打卡day30|贪心算法篇04|Leetcode 860.柠檬水找零、406.根据身高重建队列、452. 用最少数量的箭引爆气球，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
算法题
Leetcode 860.柠檬水找零
题目链接:860.柠檬水找零
大佬视频讲解：柠檬水找零视频讲解
个人思路
5元最通用，然后是10元，所以如果是对于20元找零直接先找10元，也涉及到贪心的思想，可以用贪心算法。
解法
贪心法
对于找零分为三种情况
- 情况一：账单是5，直接收下。
- 情况二：账单是10，消耗一个5，增加一个10
- 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5
局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。
class Solution {public boolean lemonadeChange(int[] bills) {int five = 0;//五元数量int ten = 0;//十元数量for (int i = 0; i < bills.length; i++) {if (bills[i] == 5) {five++;} else if (bills[i] == 10) {five--;ten++;} else if (bills[i] == 20) {if (ten > 0) {//先消耗十元ten--;five--;} else {five -= 3;}}if (five < 0 || ten < 0) return false;//遍历完如果不够找零就返回false}return true;}
}时间复杂度:O(n)；（遍历数组）
空间复杂度:O(1);（两个变量-常量级）
Leetcode 406.根据身高重建队列
题目链接:406.根据身高重建队列
大佬视频讲解：根据身高重建队列视频讲解
个人思路
这道题与昨天的分发糖果有些像，都是需要分开考虑两个维度，要先确定一个维度，再确定另一个维度。
解法
贪心法
可以先手动模拟一遍，发现只能先按照身高排序，因为前面的节点一定都比本节点高！排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。
按照题目所给例子做个示范：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]，整个插入过程如下：
排序完的people： [[7,0], [7,1], [6,1], [5,0], [5,2]，[4,4]]
插入的过程：
- 插入[7,0]：[[7,0]]
- 插入[7,1]：[[7,0],[7,1]]
- 插入[6,1]：[[7,0],[6,1],[7,1]]
- 插入[5,0]：[[5,0],[7,0],[6,1],[7,1]]
- 插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
- 插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
class Solution {public int[][] reconstructQueue(int[][] people) {// 身高从大到小排（身高相同时 k小的站前面）Arrays.sort(people, (a, b) -> {// a - b 是升序排列，故在a[0] == b[0]的状况下，会根据k值升序排列if (a[0] == b[0]) return a[1] - b[1]; //b - a 是降序排列，在a[0] != b[0]，的状况会根据h值降序排列return b[0] - a[0]; });LinkedList<int[]> que = new LinkedList<>();for (int[] p : people) {que.add(p[1],p); //将value插入到指定index里。}return que.toArray(new int[people.length][]);}
}时间复杂度:O(n log n)；（排序操作）
空间复杂度:O(n);（用
LinkedList来存储元素）
Leetcode 452. 用最少数量的箭引爆气球
题目链接:452. 用最少数量的箭引爆气球
大佬视频讲解：用最少数量的箭引爆气球视频讲解
个人思路
如何计算重叠区间呢，重叠区间是删除还是跳过，根据左边界还是右边界呢 思路不清晰...
解法
贪心法
局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。
求边界问题，为了让气球尽可能的重叠，需要对数组进行排序，排序之后，从前到后遍历气球，被射过的气球仅仅跳过就行了，再记录一下箭的数量。
按照气球起始位置排序，还是按照气球终止位置排序 都可以，这里按照起始位置排序
如果遇到气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。.
以题目示例： [[10,16],[2,8],[1,6],[7,12]]为例，如图：（方便起见，已经排序）
如上图，首先第一组重叠气球，一定是需要一个箭，气球3，的左边界大于了 第一组重叠气球的最小右边界，所以再需要一支箭来射气球3。
class Solution {public int findMinArrowShots(int[][] points) {// 根据气球直径的开始坐标从小到大排序Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0])); int count = 1; // points 不为空时,至少需要一支箭for (int i = 1; i < points.length; i++) {if (points[i][0] > points[i - 1][1]) { // 气球i和气球i-1不挨着,不能加=count++; // 需要一支箭} else { // 更新重叠气球最小右边界points[i][1] = Math.min(points[i][1], points[i - 1][1]);}}return count;}
}时间复杂度:O(n logN)；（排序数组）
空间复杂度:O( logN);（java所使用的内置函数用的是快速排序需要 logN 的空间）
以上是个人的思考反思与总结，若只想根据系列题刷，参考卡哥的网址代码随想录算法官网
这篇关于算法打卡day30|贪心算法篇04|Leetcode 860.柠檬水找零、406.根据身高重建队列、452. 用最少数量的箭引爆气球的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
