当前位置：首页 > news >正文

leetcode算法刷题的第二十五天

news 2025/9/4 5:50:17

1.leetcode 134.加油站

题目链接

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum=0;int totalSum=0;int start=0;for(int i=0;i<gas.size();i++){curSum+=gas[i]-cost[i];totalSum+=gas[i]-cost[i];if(curSum<0){// 当前累加rest[i]和 curSum一旦小于0start=i+1;// 起始位置更新为i+1curSum=0;// curSum从0开始}}//说明永远是消耗的，不可能走完一圈if(totalSum<0) return -1;// 说明怎么走都不可能跑一圈了return start;}
};

思路总结：

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

每个加油站的剩余量rest[i]为gas[i] - cost[i]。

i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。

如果 curSum<0 说明区间和1 + 区间和2 < 0，那么假设从上图中的位置开始计数curSum不会小于0的话，就是区间和2>0。

区间和1 + 区间和2 < 0 同时区间和2>0，只能说明区间和1 < 0，那么就会从假设的箭头初就开始从新选择起始位置了。

那么局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。

局部最优可以推出全局最优，找不出反例，试试贪心！

这个方法才真正体现出贪心的精髓，用局部最优可以推出全局最优，进而求得起起始位置。

2.leetcode 135.分发糖果

题目链接

class Solution {
public:int candy(vector<int>& ratings) {vector<int> candyVec(ratings.size(),1);//从前往后for(int i=1;i<ratings.size();i++){//右孩子比左孩子高if(ratings[i]>ratings[i-1]) candyVec[i]=candyVec[i-1]+1;}//从后往前for(int i=ratings.size()-2;i>=0;i--){if(ratings[i]>ratings[i+1]){//左孩子比右孩子高candyVec[i]=max(candyVec[i],candyVec[i+1]+1);}}//统计结果int sum=0;for(int i=0;i<candyVec.size();i++){sum+=candyVec[i];}return sum;}
};

思路总结：这道题目一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。

这在leetcode上是一道困难的题目，其难点就在于贪心的策略，如果在考虑局部的时候想两边兼顾，就会顾此失彼。

那么本题我采用了两次贪心的策略：

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

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

3.leetcode 860.柠檬水找零

题目链接

class Solution {
public:bool lemonadeChange(vector<int>& bills) {int five=0,ten=0,twenty=0;for(int bill : bills){//情况一if(bill==5) five++;//情况二if(bill==10){if(five<=0) return false;five--;ten++;}//情况三if(bill==20){// 优先消耗10美元，因为5美元的找零用处更大，能多留着就多留着if(five>0&&ten>0){five--;ten--;twenty++;// 其实这行代码可以删了，因为记录20已经没有意义了，不会用20来找零}else if(five>=3){five-=3;twenty++;// 同理，这行代码也可以删了}else return false;}}return true;}
};

思路总结：不知道为什么这道题用传统的for循环过不了，原来是要遍历所有的元素，用这个for循环可以避免索引错误。

这道题目刚一看，可能会有点懵，这要怎么找零才能保证完成全部账单的找零呢？

但仔细一琢磨就会发现，可供我们做判断的空间非常少！

只需要维护三种金额的数量，5，10和20。

有如下三种情况：

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

此时大家就发现情况一，情况二，都是固定策略，都不用我们来做分析了，而唯一不确定的其实在情况三。

而情况三逻辑也不复杂甚至感觉纯模拟就可以了，其实情况三这里是有贪心的。

账单是20的情况，为什么要优先消耗一个10和一个5呢？

因为美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能！

所以局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。

局部最优可以推出全局最优，并找不出反例，那么就试试贪心算法！

咋眼一看好像很复杂，分析清楚之后，会发现逻辑其实非常固定。

这道题目可以告诉大家，遇到感觉没有思路的题目，可以静下心来把能遇到的情况分析一下，只要分析到具体情况了，一下子就豁然开朗了。

如果一直陷入想从整体上寻找找零方案，就会把自己陷进去，各种情况一交叉，只会越想越复杂了。

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

题目链接

class Solution {
public:static bool cmp(const vector<int>& a,const vector<int>& b){if(a[0]==b[0]) return a[1]<b[1];return a[0]>b[0];}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {vector<vector<int>> que;sort(people.begin(),people.end(),cmp);for(int i=0;i<people.size();i++){int position=people[i][1];que.insert(que.begin()+position,people[i]);}return que;}
};

思路总结：本题有两个维度，h和k，看到这种题目一定要想如何确定一个维度，然后再按照另一个维度重新排列。

如果两个维度一起考虑一定会顾此失彼。

对于本题相信大家困惑的点是先确定k还是先确定h呢，也就是究竟先按h排序呢，还是先按照k排序呢？

如果按照k来从小到大排序，排完之后，会发现k的排列并不符合条件，身高也不符合条件，两个维度哪一个都没确定下来。

那么按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。

此时我们可以确定一个维度了，就是身高，前面的节点一定都比本节点高！

那么只需要按照k为下标重新插入队列就可以了。

局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性

全局最优：最后都做完插入操作，整个队列满足题目队列属性

局部最优可推出全局最优，找不出反例，那就试试贪心。

这道题目还是偏难的，需要好好钻研一下。

查看全文