力扣算法刷题 Day 29

134 加油站题目链接添加链接描述思路刚拿到题的思路局部最优开始时出发的那站到达下一站并准备出发时所拥有的汽油尽可能多。找到目标站后验证正确性。测试没有通过未通过的数据集如下分析问题当前代码将4作为开始位置因为其开始拥有汽油最多到达第2站时无法到达。这是因为对剩余油量rest起到正作用的3没有被用到。思考得出结论局部最优应该是净补充油量最大的子序列。换言之我们从0开始rest数组加和小于0就从下一个下标位置开始。文章详解添加链接描述classSolution{public:intcanCompleteCircuit(vectorintgas,vectorintcost){vectorintsubstract(gas.size());inttotal0;for(inti0;isubstract.size();i){substract[i]gas[i]-cost[i];totalsubstract[i];}if(total0)return-1;intstart0;intsum0;for(inti0;isubstract.size();i){sumsubstract[i];if(sum0){starti1;sum0;}}returnstart;}};135 分发糖果题目链接点击此处思路同时考虑左右两边难以下手。将任务拆解为从第一个开始如果右边的同学rating高右边比左边多1从最后一个开始如果左边的同学rating高左边 max右边 1原左边局部最优满足相邻的rating高整体最优。因为每次只加1所以也满足数量最少。文章详解添加链接描述classSolution{public:intcandy(vectorintratings){vectorintcandy_num(ratings.size(),1);for(inti0;i1ratings.size();i){if(ratings[i1]ratings[i]){candy_num[i1]candy_num[i]1;}}for(intjratings.size()-1;j-10;j--){if(ratings[j-1]ratings[j]){candy_num[j-1]max(candy_num[j]1,candy_num[j-1]);}}intans0;for(inti0;iratings.size();i){//cout candy_num[i];anscandy_num[i];}returnans;}};860 柠檬水找零题目链接点击此处思路贪心的策略体现在20块的找零先找最大的10没了再找5,保证零钱管够文章详解添加链接描述classSolution{public:boollemonadeChange(vectorintbills){intn_50;intn_100;intn_200;for(inti0;ibills.size();i){if(bills[i]5){n_5;continue;}elseif(bills[i]10){n_10;n_5--;}elseif(bills[i]20){n_20;if(n_10)//注意贪心策略找10前提有10{n_10--;n_5--;}else{n_5-3;}}if(n_50||n_100||n_200)//检查合法性{coutn_20n_10n_5endl;returnfalse;}}returntrue;}};406 根据身高重建队列题目链接添加链接描述思路局部最优左边的人比右边的人身高高且ki比右边的人小。任务拆解一下先按身高从大往小排再按其他信息调整文章详解添加链接描述classSolution{public:staticboolcmp(constvectorinta,constvectorintb){if(a[0]b[0])returna[1]b[1];returna[0]b[0];}vectorvectorintreconstructQueue(vectorvectorintpeople){sort(people.begin(),people.end(),cmp);vectorvectorintque;for(inti0;ipeople.size();i){intpositionpeople[i][1];que.insert(que.begin()position,people[i]);}returnque;}};