算法练习Day28 K 次取反后最大化的数组和
终极管理员 知识笔记 90阅读
0.
那如果是前面的数组里前部分耗油大但是后面的部分耗油很少啊为什么不从初始位置的下一个走而是结束位置后面走呢如果是这种情况不就错过了实际这也间接的可以说明我们之前[0i]的那一段后面的加油量也不够如果足够的话并不会出现这种情况所以我们在起始位置后面接着遍历也是差不多的情况而且并不会错过因为我们无论如何是要走完一周的题目已经说了如果有答案一定是唯一的所以我们肯定要先从存油大消耗少的位置出发这样也会增加一些找到答案的可能性当然具体是否能够实现肯定是要看总加油数量减去总耗油数量。
class Solution {public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int start0; int zongsum0;int sum0; for(int i0;i<gas.size();i){ zongsumgas[i]-cost[i]; sumgas[i]-cost[i]; if(sum<0){ starti1;sum0;//正好走到当前的i了油不够了。所以应该避免过早走到此处应从i1开始走把油积累起来后再走该处。 } } if(zongsum<0)return -1; return start; }};135. 分发糖果 - 力扣LeetCode
首次遇到的贪心困难题题目要求是要统计每个小孩能拿多少糖起初每个小孩只能拿一颗但是如果这个孩子比他相邻的孩子评分高那么他就可以拿到比相邻孩子多一颗的糖果这里要注意是比他相邻两个孩子拿到最多糖果那个还要多一颗这点要注意。不过要生两个孩子分数相等的话他只拿一颗糖果。
这道题的解题思路实际上是先判断从左往右或者从右往左一趟顺序下的糖果数目然后再从另一相反的方向再判断一次不要两边一起判断这样代码很难写出这里是什么意思呢就比如说{253}5比2大比3大我们不要一次性就判断出来中间孩子应该得到几颗糖而是要判断一个方向再判断一个方向最后再得出结果。
这里我们先来判断后面的评分是否大于当前评分的情况这里的判断方向是从前向后遍历遍历方向不是随机的是按照如何判断来写的这一点是经过合理的推导的。因为我们要比较的是右边数据是否大于左边我们知道右边数据如果比当前数据大那么他获得当前这个的糖果数1那么当前这个孩子的糖果数受什么影响呢受前面的那个孩子糖果数量影响这一点很重要所以我们用从前向后遍历的顺序因为这样会保证我们想要的数据都是已经确定下来的。从前向后遍历前面的糖果数肯定是确定下来的。
但是如果是判断左孩子是否大于当前孩子呢为啥这还要重复判断一次呢{253}不就是判断一次就好了嘛那如果是{2532}呢只判断一个方向的话明明3那个位置孩子得到的糖果是大于1的但是根据上面的判断右边孩子没有大于当前孩子的分数那么3这个分数就只拿到一颗糖果但是实际上它的分数比相邻的2要大他拿到2颗糖果是没有问题的这也是为什么我们要对相反方向再做一次判断。说完了这个原因下一个值的注意的点是在第二次的遍历中如果发现左孩子大于了右孩子那么要比较右孩子的糖果数1得到的多还是左孩子本身拥有的糖果数量多取最大的那个因为如果数据序列像{25611}这样的在第一次遍历比较时候6分的孩子就拿到了三块糖果但是从后向前遍历时他只能拿到两颗那么肯定是不行的他拿到三颗是正确的为了避免中间数比左右两边都大的时候出现一些意想不到的错误所以我们第二次遍历要取两者最大数作为获得糖果数量更新数组。
class Solution {public: int candy(vector<int>& ratings) { vector<int>candys(ratings.size(),1);int count0; for(int i1;i<ratings.size();i){ if(ratings[i]>ratings[i-1]) candys[i]candys[i-1]1; } for(int iratings.size()-1;i>0;i--){ if(ratings[i-1]>ratings[i]) candys[i-1]max(candys[i-1],candys[i]1); } for(int i0;i<candys.size();i)countcandys[i]; return count; }};今天我们完成了K 次取反后最大化的数组和、加油站、分发糖果三道题相关的思想需要多复习回顾。接下来我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。
当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~