代码随想录算法训练营day29 | 134. 加油站、135. 分发糖果、860.柠檬水找零、406.根据身高重建队列

碎碎念：加油
参考：代码随想录

134. 加油站

题目链接

134. 加油站

思想

在这里插入图片描述
局部最优： 一旦currentSum为负数，起始位置至少要是i+1。
全局最优： 最后可以跑完一圈。
局部最优可以推出全局最优且找不到反例，所以用贪心试一下。
我们关心的是经过补充和消耗油量，净增还是净减了油量。
用一个遍历currentSum来累加每个站剩余的油量，一旦currentSum变为负数，说明这个站点之前的每个站点作为起始位置都不行，所以此时要往后遍历，继续用currentSum来统计剩余油量。

题解

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int currentSum = 0;int totalSum = 0;int start = 0;for (int i = 0; i < gas.size(); i++) {currentSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if (currentSum < 0) {start = i + 1;currentSum = 0;}}if (totalSum < 0) return -1;return start;}

class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:currentSum = 0totoalSum = 0start = 0for i in range(len(gas)):currentSum += gas[i] - cost[i]totoalSum += gas[i] - cost[i]if currentSum < 0:start = i + 1currentSum = 0if totoalSum < 0:return -1return start

反思

135. 分发糖果

题目链接

135. 分发糖果

思想

确定分发糖果数的时候既要考虑当前孩子左边的情况，还要考虑右边的情况，这就要求我们分开考虑。先确定一边的情况，再去确定另一边。
在这里插入图片描述
局部最优：

右边小孩比左边小孩得分高的情况
左边小孩比右边小孩得分高的情况【需要从后往前遍历】

这样从局部最优就能推出全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。
最后把遍历把candy累加起来。

题解

// cpp
class Solution {
public:int candy(vector<int>& ratings) {vector<int> candy(ratings.size(), 1);// 从前往后，右边小孩比左边小孩得分高的情况for (int i = 1; i < ratings.size(); i++) {if (ratings[i] > ratings[i - 1]) candy[i] = candy[i - 1] + 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 result = 0;for (int i = 0; i < candy.size(); i++) result += candy[i];return result;} 
};

# python
class Solution:def candy(self, ratings: List[int]) -> int:candy = [1] * len(ratings)for i in range(1, len(ratings)):if ratings[i] > ratings[i - 1]:candy[i] = candy[i - 1] + 1for i in range(len(ratings) - 2, -1, -1):if ratings[i] > ratings[i + 1]:candy[i] =  max(candy[i], candy[i + 1] + 1)result = 0for i in range(len(candy)):result += candy[i]return result

反思

注意要两个方面分别考虑，注意for循环的范围。

860.柠檬水找零

题目链接

860.柠檬水找零

思想

局部最优： 收到20的时候优先用10+5来找零（把更万能的5留下）
全局最优： 正确找零
局部最优可以推出全局最优且找不到反例，试试贪心。
收钱遇到的几种情况：

5 直接收了
10 用5找零
20 用10+5或5+5+5找零，优先使用10+5找零。

定义三个变量，five，ten，twenty来记录收到的钞票数量。
其实20的数量可以不记录，因为找零用不到。

题解

// cpp
class Solution {
public:bool lemonadeChange(vector<int>& bills) {int five = 0, ten = 0;for (int bill : bills) {if (bill == 5) five++;if (bill == 10) {if (five == 0) return false;ten++;five--;}if (bill ==20) {if (ten >0 && five > 0){ten--;five--;} else if (five >= 3) {five -= 3;} else return false;}}return true;}
};

# python
class Solution:def lemonadeChange(self, bills: List[int]) -> bool:five = 0ten = 0for bill in bills:if bill == 5:five += 1if bill == 10:if five > 0:five -= 1ten += 1else:return Falseif bill == 20:if five > 0 and ten > 0:five -= 1ten -= 1elif five >= 3:five -= 3else:return Falsereturn True

406.根据身高重建队列

题目链接

406.根据身高重建队列

思想

本题的思想有点像上面做的分发糖果问题，都需要两头考虑，如果同时考虑很容易出错。
局部最优： 优先按身高高的people的k来插入。插入操作过后的people满足队列属性。
全局最优： 最后都做完插入操作，整个队列满足题目队列属性。
局部最优可以推出全局最优且找不到反例，试试贪心。
需要两个维度分开考虑。

按照h从小到大排列，如果h相等，按照k从小到大排列
根据k的大小来调整排序，根据k来插入对应位置

题解

// cpp
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) {sort (people.begin(), people.end(), cmp);vector<vector<int>> que;for (int i = 0; i < people.size(); i++) {int position = people[i][1];que.insert(que.begin() + position, people[i]);}return que;}
};

# python
class Solution:def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:# 先按每个元素的第一个值进行降序排序。# 如果第一个值相同，则按每个元素的第二个值进行升序排序。people.sort(key = lambda x:(-x[0], x[1]))que = []for p in people:que.insert(p[1], p)return que