代码随想录算法训练营第三十五天| 860.柠檬水找零，406.根据身高重建队列，452. 用最少数量的箭引爆气球

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

题目与题解

860.柠檬水找零

题目链接：860.柠檬水找零

代码随想录题解：860.柠檬水找零

视频讲解：贪心算法，看上去复杂，其实逻辑都是固定的！LeetCode：860.柠檬水找零_哔哩哔哩_bilibili

解题思路：

从现实实际的角度出发，为了让手里的零钱尽可能的零碎，以备不时之需，需要找钱时肯定尽量能先找大的就找大的。这道题其实限制颇多，给解题降低了不少难度。

首先，每个顾客只买一份柠檬水，意味着每个顾客每次消费的金额固定，为5美金。其次，顾客每次只会给5，10，20美金的面额，所以对应的情况是不需要找钱，找5美金，和找15美金。前两种的情况对应的找钱都是固定的，只有找15美金时可能有两种情况：找10+5或5*3。为了手里有更多5美金的零钱，优先找10+5的。代码如下

class Solution {public boolean lemonadeChange(int[] bills) {int[] changes = new int[2];for (int i = 0; i < bills.length; i++) {if (bills[i] == 5) {changes[0]++;} else if (bills[i] == 10) {if (changes[0] > 0) {changes[0]--;changes[1]++;} else {return false;}} else {if (changes[1] > 0 && changes[0] > 0) {changes[0]--;changes[1]--;} else if (changes[0] >= 3) {changes[0] -= 3;} else {return false;}}}return true;}
}

看完代码随想录之后的想法

这题其实就是现实的模拟题，基本上也没有什么算法可言，就是把想法写下来。由于这里只需要算5美金和10美金的两种剩余零钱情况，可以不需要用数组，换成普通变量记录，效率更高。

遇到的困难

无

406.根据身高重建队列

题目链接：406.根据身高重建队列

代码随想录题解：406.根据身高重建队列

视频讲解：贪心算法，不要两边一起贪，会顾此失彼 | LeetCode：406.根据身高重建队列_哔哩哔哩_bilibili

解题思路：

首先根据身高进行降序排列，如果身高相同的，根据k降序排列。这样做的原因是，身高排序问题本质是一种插入排序，所以每插入一个新的，要保证原来的顺序不受影响。由于身高高的k值不受身高低的k值影响，所以排序的第一个key必然是身高。当二者身高相同时，k值越大的，肯定排的越后，所以优先插入k值小的。

二维排序结束后，就要按顺序逐一插入队伍了，直接根据当前people[i]的k值，将people[i]插入对应的k位置即可，这样可以保证people[i]的前面不比他矮的人数就是k。

class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, new Comparator<int[]>() {public int compare(int[] o1, int[] o2) {if(o1[0] != o2[0]){return o2[0] - o1[0];  //身高降序排列} else {return o1[1] - o2[1];  //前方需要插入人数升序排列}}});List<int[]> result = new ArrayList<>();for (int i = 0; i < people.length; i++) {result.add(people[i][1], people[i]);}return result.toArray(new int[people.length][]);}
}

看完代码随想录之后的想法

一开始写排序算法重写了很多次，一直没有想清楚插入排序之前的数组应该如何优先排序，所以怎么都写不对。偷看了一下随想录的排序方法，才写对compare函数。

此外，虽然list类型可以用来进行插入排序，但其底层实现毕竟是数组，效率不高，换成链表会更好。

class Solution {public int[][] reconstructQueue(int[][] people) {// 身高从大到小排（身高相同k小的站前面）Arrays.sort(people, (a, b) -> {if (a[0] == b[0]) return a[1] - b[1];   // a - b 是升序排列，故在a[0] == b[0]的狀況下，會根據k值升序排列return b[0] - a[0];   //b - a 是降序排列，在a[0] != b[0]，的狀況會根據h值降序排列});LinkedList<int[]> que = new LinkedList<>();for (int[] p : people) {que.add(p[1],p);   //Linkedlist.add(index, value)，會將value插入到指定index裡。}return que.toArray(new int[people.length][]);}

遇到的困难

对于多维度的贪心，还是要一个一个维度想清楚具体的贪心方法，再结合起来，不然很容易想错。

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

题目链接：452. 用最少数量的箭引爆气球

代码随想录题解：452. 用最少数量的箭引爆气球

视频讲解：贪心算法，判断重叠区间问题 | LeetCode：452.用最少数量的箭引爆气球_哔哩哔哩_bilibili

解题思路：

题目已经提醒了，这道题本质就是求相交区间的问题。如果多个区间同时相交，就只需要一根箭。

因此，可以先对区间进行排序，以左边界为第一关键字，右边界为第二关键字，得到排序后的区间。然后用arrowPoint记录当前相交区间的范围，初始化为第一个区间的大小，此时需要的箭数量为1。然后遍历所有的区间，如果当前区间的左边界大于arrowPoint右边界，说明区间不相交，所需箭的数量加一，arrowPoint更新为当前区间范围；否则说明当前区间与arrowPoint有相交，此时更新arrowPoint的右边界为二者右边界的更小值即可。

class Solution {public int findMinArrowShots(int[][] points) {if (points.length <= 1) return points.length;Arrays.sort(points, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {if (o1[0] == o2[0])return Integer.compare(o1[1], o2[1]);return Integer.compare(o1[0], o2[0]);}});int count = 1;int[] arrowPoint = points[0];for (int i = 1; i < points.length; i++) {if (points[i][0] > arrowPoint[1]) {count++;arrowPoint = points[i];} else {arrowPoint[0] = points[i][0];arrowPoint[1] = Math.min(arrowPoint[1], points[i][1]);}}return count;}
}

看完代码随想录之后的想法

有一些可以优化的地方：区间排序其实只需要针对左边界，右边界可以不需要；arrowPoint也可以直接用当前point代替，减少一点变量的使用。不过这样涉及到修改point数组了，个人不是特别喜欢。

/*** 时间复杂度 : O(NlogN)  排序需要 O(NlogN) 的复杂度* 空间复杂度 : O(logN) java所使用的内置函数用的是快速排序需要 logN 的空间*/
class Solution {public int findMinArrowShots(int[][] points) {// 根据气球直径的开始坐标从小到大排序// 使用Integer内置比较方法，不会溢出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 {  // 气球i和气球i-1挨着points[i][1] = Math.min(points[i][1], points[i - 1][1]); // 更新重叠气球最小右边界}}return count;}
}