代码随想录 day 29 贪心

第八章 贪心算法 part03

134. 加油站

本题有点难度，不太好想，推荐大家熟悉一下方法二
https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html

135. 分发糖果

本题涉及到一个思想，就是想处理好一边再处理另一边，不要两边想着一起兼顾，后面还会有题目用到这个思路
https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html

860.柠檬水找零

本题看上好像挺难，其实很简单，大家先尝试自己做一做。
https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html

406.根据身高重建队列

本题有点难度，和分发糖果类似，不要两头兼顾，处理好一边再处理另一边。
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

134. 加油站

题目链接

https://leetcode.cn/problems/gas-station/description/

解题思路

首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。

i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。
局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。
局部最优可以推出全局最优，找不出反例，试试贪心！

code

class Solution {//贪心  局部油量总和小于0 更新i为i+1   全局 总油量大于花费的油量 得出ipublic int canCompleteCircuit(int[] gas, int[] cost) {int curSum=0;int res=0;int rest=0;for(int i=0;i<gas.length;i++){curSum+=gas[i]-cost[i];rest+=gas[i]-cost[i];if(curSum<0){curSum=0;res=i+1;}}return rest>=0?res:-1;}
}

暴力解法，模拟一圈用while循环的思想挺好，值得学习。

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {for(int i=0;i<gas.length;i++){if(gas[i]-cost[i]<0){continue;}int count=gas[i]-cost[i];//记录剩余油量//记录下一个位置int index = (i + 1) % gas.length;while(count>=0&&index!=i){//模拟以i为起点行驶一圈count+=(gas[index]-cost[index]);//更新油量index=(index+1)%gas.length;//更新下一个位置}if(count>=0&&i==index){return i;}}return -1;}
}

135. 分发糖果

题目链接

https://leetcode.cn/problems/candy/description/

解题思路

这道题目一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。
1.先确定右边评分大于左边的情况（也就是从前向后遍历）
此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
局部最优可以推出全局最优。
2.再确定左孩子大于右孩子的情况（从后向前遍历）
局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。
局部最优可以推出全局最优。
总结
那么本题我采用了两次贪心的策略：

• 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
• 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。

这样从局部最优推出了全局最优，即：相邻的孩子中，评分高的孩子获得更多的糖果

code

class Solution {public int candy(int[] ratings) {int[] candy=new int[ratings.length];Arrays.fill(candy,1);//右比左大for(int left=1;left<ratings.length;left++){if(ratings[left]>ratings[left-1]){candy[left]=candy[left-1]+1;}}//左比右大for(int right=ratings.length-2;right>=0;right--){if(ratings[right]>ratings[right+1]){//这个为什么使用max是上一个循环记录了右比左大，当前循环是记录左比右大//如果右比左大，是要取一个最大值的，满足即大于左也大于右才行。candy[right]=Math.max(candy[right+1]+1,candy[right]);}}return Arrays.stream(candy).sum();}
}

60.柠檬水找零

题目链接

https://leetcode.cn/problems/lemonade-change/description/

解题思路

按题目模拟就好了。
记录变量刚开始用集合记录值了，实际用个int变量记录就好。

这题的贪心，实在想不出，看了题解说是 20美元优先使用10

• 情况一：账单是5，直接收下。
• 情况二：账单是10，消耗一个5，增加一个10
• 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5

贪心在情况三

因为美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能！
所以局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。

code

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

406.根据身高重建队列

题目链接

https://leetcode.cn/problems/queue-reconstruction-by-height/description/

解题思路

那么按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面,按照身高排序之后，优先按身高高的people的k来插入

所以在按照身高从大到小排序后:
局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优：最后都做完插入操作，整个队列满足题目队列属性

code

class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people,(a,b)->{if(a[0]==b[0]){//身高相同 按k升序 也就是k大的在后return a[1]-b[1];}return b[0]-a[0];//按身高降序});LinkedList<int[]> que=new LinkedList<>();for(int[] p:people){//Linkedlist.add(index, value) value插入到index位置que.add(p[1],p);}return que.toArray(new int[people.length][]);}
}