代码随想录第29天|贪心算法part3

本文主要是介绍代码随想录第29天|贪心算法part3，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

134.加油站

在这里插入图片描述
首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈
每个加油站的剩余量rest[i]为gas[i] - cost[i]
从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置
因为我们一直维护的是一个剩余量大于等于0的区间，如果突然小于0，那么可以思考，从start到i中任取一个位置j作为起点，则j到i位置所得到的剩余量和一定小于0, 累加和cursum [start,j] > 0,[start,i] <0,而i>j,所以[j,i]必定<0
所以我们需要重新选择起始点,start=i+1，cursum=0,重新开始计算剩余量
在这里插入图片描述

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){start = i + 1;cursum = 0;}}if(totalSum < 0) return -1;return start;}
};

135.分发糖果

在这里插入图片描述
这道题目一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。
局部最优：右边的孩子如果分数比左边大，就比左边多一颗
全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
但是单看右孩子还是无法满足题目条件，如
ratings:
[1,8,8,2,1]
光用右孩子会得到
[1,2,1,1,1]
这明显不满足条件，因为8比2大，2比1大，所以需要看左孩子
而且要从后向前遍历，因为r[i]和r[i-1]的比较要用上r[i]和r[i+1]的比较结果（糖果数)
如果 ratings[i] > ratings[i + 1]，此时candyVec[i]（第i个小孩的糖果数量）就有两个选择了，一个是candyVec[i + 1] + 1（从右边这个加1得到的糖果数量），一个是candyVec[i]（之前比较右孩子大于左孩子得到的糖果数量）。
局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。
取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多，也比右边candyVec[i + 1]的糖果多。

class Solution {
public:int candy(vector<int>& ratings) {vector<int> candy(ratings.size(), 0);candy[0] = 1;for (int i = 1; i < ratings.size(); i++) {if (ratings[i] > ratings[i - 1])candy[i] = candy[i - 1] + 1;elsecandy[i] = 1;}for (int i = ratings.size() - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {candy[i] = max(candy[i], candy[i + 1] + 1);}}int sum = 0;for (int m : candy) {sum += m;}return sum;}
};

860.柠檬水找零

在这里插入图片描述
记录收到的钞票数，如果是5元就拿着，10元就判断是否有5元剩余，
20元就首先判断有没有1个10元和1个5元，没有就判断有没有3个5元

class Solution {
public:bool lemonadeChange(vector<int>& bills) {vector<int> pay(3, 0);for (int i = 0; i < bills.size(); i++) {if (bills[i] == 5) {pay[0]++;} else if (bills[i] == 10) {if (pay[0] == 0)return false;pay[0]--;pay[1]++;} else {if (pay[0] == 0)return false;else {if (pay[1] != 0) {pay[1]--;pay[0]--;} else {if (pay[0] < 3)return false;elsepay[0] -= 3;}}}}return true;}
};

406.根据身高重建队列

在这里插入图片描述
遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。
如果按照k来从小到大排序，排完之后，会发现k的排列并不符合条件，身高也不符合条件，两个维度哪一个都没确定下来。

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

此时我们可以确定一个维度了，就是身高，前面的节点一定都比本节点高！
首先按身高从高到低排序，然后从前往后遍历，如果有2个人比这个人高，则插入到下标为2的位置即可（前面两个人比他高）
在这里插入图片描述
局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性

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

class Solution {
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(), people.end(), [](vector<int> a, vector<int> b) {if (a[0] == b[0])return a[1] < b[1];return a[0] > b[0];});list<vector<int>> res;for (int i = 0; i < people.size(); i++) {int pos = people[i][1];auto it = res.begin();while(pos){it++;pos--;}res.insert(it,people[i]);}return vector<vector<int>>(res.begin(),res.end());}
};