算法笔记|Day25贪心算法III

☆☆☆☆☆leetcode 134. 加油站

题目链接：leetcode 134. 加油站

题目分析

用cur表示走到i时剩余油量，sum表示总的剩余油量，start表示开始出发时的位置（默认为0）。若cur出现小于0的情况，说明无法到达，则从下一个位置重新开始（即把i+1赋值给start）并恢复剩余油量cur为0；若结束总sum小于0，说明无法走一圈返回-1；否则返回开始位置start。

代码

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int cur=0,sum=0,start=0;for(int i=0;i<gas.length;i++){cur+=gas[i]-cost[i];sum+=gas[i]-cost[i];if(cur<0){cur=0;start=i+1;}}if(sum<0)return -1;return start;}
}

☆☆☆☆☆leetcode 135. 分发糖果

题目链接：leetcode 135. 分发糖果

题目分析

此题需要考虑从左到右和从右到左两个方向，应分别考虑。首先每个孩子分发一个糖果（依次遍历candies数组并赋值为1），从左到右遍历，若比前一个孩子的分数高，则在前一个孩子得到糖果的基础上加一；再从右到左考虑，若需要在后一个孩子得到糖果的基础上加一，同时还要满足第一种情况，需要取两者最大值（也就是和第一种情况分发后的糖果数相比取最大值）；最后遍历糖果数求和即可。

代码

class Solution {public int candy(int[] ratings) {int candies[]=new int[ratings.length];for(int i=0;i<candies.length;i++)candies[i]=1;for(int i=1;i<ratings.length;i++){if(ratings[i]>ratings[i-1])candies[i]=candies[i-1]+1;}for(int i=ratings.length-2;i>=0;i--){if(ratings[i+1]<ratings[i])candies[i]=Math.max(candies[i+1]+1,candies[i]);}int res=0;for(int candy:candies)res+=candy;return res;}
}

☆☆☆☆☆leetcode 860.柠檬水找零

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

题目分析

依次遍历bills数组中的值，有三种情况：①收入5元，five加一，不会出现false情况；②收入10元，若有5元则five减一且ten加一，否则返回false；③收入20元，若有至少一张5元且有至少一张10元则five减一ten减一，若没有上述情况但有至少三张5元则five减三，否则返回false。若遍历结束，仍无false情况则返回true。

代码

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

☆☆☆☆☆leetcode 406.根据身高重建队列

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

题目分析

首先将people数组排序，按高度h降序排列，若高度h相同，按照前面有k个身高大于或等于h人中的k升序排列，这样只需要从高到低依次按索引k插入新的链表即可。

代码

class Solution {public int[][] reconstructQueue(int[][] people) {List<int[]> resList=new LinkedList<>();Arrays.sort(people,(a,b)->{if(a[0]==b[0]) return a[1]-b[1];return b[0]-a[0];});for(int p[]:people){resList.add(p[1],p);}return resList.toArray(new int[people.length][]);}
}

提示：
Arrays.sort(people,(a,b)->{
if(a[0]==b[0]) return a[1]-b[1];
return b[0]-a[0];
为Lambda表达式（也称为Lambda函数或Lambda方法）是一种简洁地表示匿名方法的方式。Lambda表达式主要用于实现只有一个抽象方法的接口（这样的接口被称为函数式接口）。