夸父追日：第八章贪心算法 part03

本文主要是介绍夸父追日：第八章贪心算法 part03，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今日收获：加油站，分发糖果，柠檬水找零，根据身高重建队列

1. 加油站

题目链接：134. - 力扣（LeetCode）

思路：

（1）局部最优是剩余油量和要大于0，否则选下一个节点作为起始节点

（2）记录当前剩余油量和总的剩余油量，如果当前剩余油量小于0，选择下一个节点作为起点。思路有点像最大子序和；如果总的剩余油量小于0，说明无解

方法：

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int len=gas.length;int totalSum=0;int curSum=0;int start=0;for (int i=0;i<len;i++){curSum+=gas[i]-cost[i];totalSum+=gas[i]-cost[i];if (curSum<0){  // 选择下一个节点开始start=i+1;curSum=0;}}if (totalSum<0){  // 无解return -1;}return start;}
}

总结：

（1）如果用暴力法将每个节点作为起始节点试一遍，for适合从头到尾的遍历，while适合模拟循环遍历

（2）对于包装过的场景题，要抽象成数据结构问题，不要生硬地跟着它的解题思路走。

2. 分发糖果

题目链接：135. - 力扣（LeetCode）

思路：

（1）第一次贪心：从左向右遍历，如果右边的孩子评分大于左边的，那么就获得比左边孩子多一个的糖果（相等不算）

（2）第二次贪心：从右向左遍历，如果左边的孩子评分大于右边的，就要将右边的孩子糖果数加1和当前孩子的糖果比较取最大值，保证中间孩子的糖果数大于两边的。

方法：

class Solution {public int candy(int[] ratings) {int len=ratings.length;int[] candy=new int[len];// 从左向右遍历candy[0]=1;for (int i=1;i<len;i++){if (ratings[i]>ratings[i-1]){candy[i]=candy[i-1]+1;continue;}candy[i]=1;}// 从右向左遍历for (int i=len-2;i>=0;i--){if (ratings[i]>ratings[i+1]){candy[i]=Math.max(candy[i+1]+1,candy[i]);}}// 计算总和int sum=0;for (int i=0;i<len;i++){sum+=candy[i];}return sum;}
}

3. 柠檬水找零

题目链接：860. - 力扣（LeetCode）

思路：遇到20美元，优先用10美元找零（局部最优）

（1）遇到5美元，直接收下

（2）遇到10美元，找零5美元

（3）遇到20美元，优先用一个10美元和5美元找零；如果没有就用三个5美元找零

方法：

class Solution {public boolean lemonadeChange(int[] bills) {int five=0;int ten=0;  // 20美元不能找零所以不记录for (int i=0;i<bills.length;i++){if (bills[i]==5){five++;continue;}if (bills[i]==10){if (five<=0){return false;  // 找不开}five--;ten++;continue;}if (bills[i]==20){if (five>0&&ten>0){  // 优先用10找零ten--;  five--;}else if (ten==0&&five>=3){five-=3;}else {return false;  // 找不开}}}return true;}
}

总结：只需要记录5和10的个数，20美元不能用于找零

4. 根据身高重建队列

题目链接：406. - 力扣（LeetCode）

思路：个子高的人调整不会影响到后面个子低的人做调整（局部最优）。按身高从大到小排列，如果身高相同，按K升序排列；然后从个子高到个子低遍历，将每个人的k值做为结果数组的下标。

方法：

class Solution {public int[][] reconstructQueue(int[][] people) {// 按身高从大到小排列，如果身高相同，按K升序排列Arrays.sort(people,(p1,p2)->{if (p1[0]==p2[0]){return p1[1]-p2[1];}return p2[0]-p1[0];});LinkedList<int[]> queue=new LinkedList<>();// 按k的值为下标排序for (int[] p:people){queue.add(p[1],p);  // index,value}// 转换为数组return queue.toArray(new int[people.length][]);}
}

总结：

（1）代码随想录：遇到两个维度需要权衡，一定要先确定一个维度，再考虑另外一个维度

（2）数组排序的lambda表达式规则：