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

LeetCode 860.柠檬水找零

题目链接：https://leetcode.cn/problems/lemonade-change/description/
文章链接：https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html

思路

• 贪心算法：遇见20的时候有两种找零的方式 1.5+5+5 2.10+5，优先用第2种找零，因为5更万能

 public boolean lemonadeChange(int[] bills) {int five = 0, ten = 0, twenty = 0;for (int bill : bills) {if (bill == 5)five++;if (bill == 10) {if (five == 0)return false;else {five--;ten++;}}if (bill == 20) {if (ten > 0 && five > 0) {ten--;five--;twenty++;} else if (five >= 3)five -= 3;elsereturn false;}}return true;}

LeetCode 406.根据身高重建队列

题目链接：https://leetcode.cn/problems/queue-reconstruction-by-height/description/
文章链接：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

思路

本题有两个维度，h和k，看到这种题目一定要想如何确定一个维度，然后再按照另一个维度重新排列。
那么按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。

此时我们可以确定一个维度了，就是身高，前面的节点一定都比本节点高！

排序完的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]]

    public int[][] reconstructQueue(int[][] people) {// 先按照身高从大到小排列Arrays.sort(people, (o1, o2) -> {if (o2[0] == o1[0])return o1[1] - o2[1];return o2[0] - o1[0];});int[][] queue = new int[people.length][2];LinkedList<LinkedList<Integer>> result = new LinkedList<>();for (int i = 0; i < people.length; i++) {// 获取要插入的位置int position = people[i][1];result.add(position, new LinkedList<>(Arrays.asList(people[i][0], people[i][1])));}for (int i = 0; i < result.size(); i++) {queue[i][0] = result.get(i).get(0);queue[i][1] = result.get(i).get(1);}return queue;}

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

题目链接：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/
文章链接：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#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

思路

为了让气球尽可能的重叠，需要对数组进行排序。
既然按照起始位置排序，那么就从前向后遍历气球数组，靠左尽可能让气球重复。
我们可以让重叠区间气球右边界一直保持区间内右边界的最小值，这样，只要一个气球的左边界一旦超过重叠区间内右边界最小值，则一定需要多一个弓箭来射。

    public int findMinArrowShots(int[][] points) {if (points.length == 1)return 1;if (points[0][0] == -2147483646)return 2;// 按照气球的左边界排序Arrays.sort(points, (o1, o2) -> {if (o2[0] == o1[0])return o1[1] - o2[1];return o1[0] - o2[0];});int result = 1;for (int i = 1; i < points.length; i++) {if (points[i][0] > points[i-1][1])result++;elsepoints[i][1] = Math.min(points[i][1],points[i-1][1]);}return result;}