LeetCode 860 柠檬水找零
题目链接：860. 柠檬水找零 - 力扣（LeetCode）
【解题思路】
-
情况1、客户支付5元的钞票——直接收下，不用找零
-
情况2、客户支付10元钞票：
-
如果手里有5元钞票，进行找零
-
如果手里没有5元钞票，return false
-
-
情况3、客户支付20元钞票：
-
如果手里有10/5元钞票：
-
策略1、用10元+5元组合找零（优先选择策略1）
-
策略2、用三个五元的组合找零
-
-
如果手里没有10/5元钞票，return false
-
【解题步骤】
-
1.定义三个变量：five，ten，twenty分别记录我们手头上对应面额的钞票
-
2.遍历账单：
-
1.如果bill == 5
-
five+1
-
-
2.如果bill == 10
-
如果five == 0，return false
-
如果five != 0,，ten +1，five - 1
-
-
3.如果bill == 20
-
如果ten大于0且five大于0
-
ten -1
-
five - 1
-
twenty + 1
-
-
如果ten等于0且five 大于等于3
-
five - 3
-
fwenty +1
-
-
如果ten等于0或者five小于3
-
return false
-
-
-
-
5.如果直到循环结束，都没有走到return false的逻辑，说明我们可以对所有账单找零，return true
【代码部分】
class Solution {public boolean lemonadeChange(int[] bills) {int ten = 0;int five = 0;int twenty = 0;for(int bill : bills){if(bill == 5){five ++;}if(bill == 10){if(five == 0){return false;}else{ten++;five--;}}if(bill == 20){if(five != 0 && ten !=0){five--;ten--;twenty++;}else if(five >= 3){five -= 3;twenty++;}else{return false;}}}return true;}
}LeetCode 406 根据身高重建队列
题目链接：406. 根据身高重建队列 - 力扣（LeetCode）
【解题思路】
-
注意！必须先处理一个维度，再处理另一个维度，比如可以先处理身高，再处理人数
-
先将数组按照身高从大到小排，如果身高相同，则按照k从小到大排
-
再按照k调整队列
【解题步骤】
-
1.按照身高从高到低给队列排序
-
2.定义一个二位数组队列，保存所有人的属性
-
3.遍历数组：
-
1）获取当前人所要插入的位置
-
2）根据插入位置在队列中进行插入当前的人
-
-
5.返回当前队列
【代码部分】
class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people,(a,b)->{if(a[0] == b[0])return a[1] - b[1];//a-b为升序排列，意思是当h相同的时候，按照k进行升序排列return b[0] - a[0];//b-a为降序排列，意思是按照身高进行降序排列});LinkedList<int[]>que = new LinkedList<>();for(int[] p : people){que.add(p[1],p);//将指定元素插入到需要插入的位置，因为是降序排列，因此k值可以理解成当前元素需要插入的位置}return que.toArray(new int[people.length][]);}
}LeetCode 452 用最少数量的箭引爆气球
题目链接：452. 用最少数量的箭引爆气球 - 力扣（LeetCode）
【解题思路】
-
尽量让弓箭在气球重叠的区间射出
-
1.按照左边界或右边界给气球进行排序，尽量让重叠的气球相邻
-
2.我按照左边界来排，因此如果当前气球的左边界大于前一个气球的右边界，意味着这两个气球不重叠，需要添加一个弓箭
-
3.如果当前气球的左边界小于等于前一个气球的右边界，意味着这两个气球重叠，不需要添加弓箭
-
但是需要将右边界更新为两个气球重叠的最小值
-
【解题步骤】
-
1.判断数组大小，如果等于0，则return 0；
-
2.对数组的左边界进行排序
-
3.定义一个result，初始化为1，记录弓箭的使用数量
-
3.遍历数组（i从1开始，因为比较的时候是i-1和i进行比较，从0开始会出现负数）：
-
1）如果当前气球左边界大于上一个气球的右边界：
-
result++
-
-
2）如果当前气球左边界小于等于上一个气球的右边界：
-
更新当前气球的右边界至两个气球重叠的最小值
-
-
-
5.return result
【代码部分】
class Solution {public int findMinArrowShots(int[][] points) {if(points.length == 0)return 0;Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));//用Integer内置的比较方法不会溢出int result = 1;for(int i = 1; i < points.length ; i++){if(points[i][0] > points[i - 1][1]){result++;}else{points[i][1] = Math.min(points[i][1],points[i-1][1]);}}return result;}
}
