代码随想录算法训练营day29

代码随想录算法训练营

—day29

---

前言

今天是算法营的第29天，希望自己能够坚持下来！
今日任务：
● 134. 加油站
● 135. 分发糖果
● 860.柠檬水找零
● 406.根据身高重建队列

---

一、134. 加油站

题目链接
文章讲解
视频讲解

暴力解法

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {for (int i = 0; i < cost.size(); i++) {int rest = gas[i] - cost[i]; // 记录剩余油量int index = (i + 1) % cost.size();while (rest > 0 && index != i) { // 模拟以i为起点行驶一圈（如果有rest==0，那么答案就不唯一了）rest += gas[index] - cost[index];index = (index + 1) % cost.size();}// 如果以i为起点跑一圈，剩余油量>=0，返回该起始位置if (rest >= 0 && index == i) return i;}return -1;}
};

---

贪心算法

思路：

1. 如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
2. 每个加油站的剩余量rest[i]为gas[i] - cost[i]。
3. i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。

解释第三点：
有没有可能 [0，i] 区间 选某一个作为起点，累加到 i这里 curSum是不会小于零呢？

如果是区间2开始累加不小于0，但从区间1+区间2是小于0的，可以得出区间1是小于0的。
但根据我们的代码逻辑，只要小于0就会更新起始位置，那么在遍历到区间1和区间2之间的时候就已经更新起始位置了，不会一直加到当前这个位置。

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) { //当前累加值小于0start = i + 1; //更新起始位置到i+1curSum = 0; //重新累加}}if (totalSum < 0) return -1; //说明不可能跑完一圈return start; //totalSum>=0时,将start之前的累加看作A, 之后的累加看作B, 已知A+B = total>=0，A<0,B>0,//那么B>|A|也就是B>=-A, 所以B+A>=0, 从start点出发可以跑完}
};

---

二、135. 分发糖果

题目链接
文章讲解
视频讲解

思路：
当有两个维度需要考虑的时候，先考虑其中一边，再考虑另一边。
本题是先考虑右孩子是否评分比较高，再考虑做孩子是否评分比较高。
1.创建一个糖果数数组，初始化为1（每个小孩至少有一个糖果）；
2.从第二个元素开始从前往后遍历，判断当前元素是否比左边元素大；
3.是则当前元素需要比左边元素糖果+1；
4.从倒数第二个元素开始从后往前遍历，判断当前元素是否比右边元素大；
5.是则当前元素比右边元素糖果+1，与第一次遍历的结果做比较，取两者最大值；
6.遍历糖果数组计算糖果总数。

对于第二次遍历为什么要从后往前遍历：
因为取糖果+1的时候是取右边的糖果+1，如果是从前往后的话，右边的糖果是一直更新的，那么就导致当前正确的糖果数也一直需要更新。

代码如下：

class Solution {
public:int candy(vector<int>& ratings) {vector<int> candys(ratings.size(), 1);//从第二个元素开始从前往后遍历，判断当前元素是否比左边元素大for (int i = 1; i < ratings.size(); i ++) {if (ratings[i] > ratings[i - 1]) candys[i] = candys[i - 1] + 1;}//从倒数第二个元素开始从后往前遍历，判断当前元素是否比右边元素大for (int i = ratings.size() - 2; i >= 0; i --) {if (ratings[i] > ratings[i + 1]) {candys[i] = max(candys[i], candys[i + 1] +  1);} }int result = 0;for (int candy:candys) {result += candy;}return result;}
};

---

三、860. 柠檬水找零

题目链接
文章讲解
视频讲解

思路：
记录拿到的5美金，10美金的张数。分三种情况处理：
1.收到5美金，直接5美金数量+1；
2.收到10美金，10美金数量+1,5美金数量-1；
3.收到20美金，优先找一张10美金和5美金；当没有10美金时，找3张5美金。

代码如下：

    class Solution {public:bool lemonadeChange(vector<int>& bills) {int num5 = 0;int num10 = 0;for (int i = 0; i < bills.size(); i++) {if (bills[i] == 5) num5++; //5美金++else if (bills[i] == 10) { //找5美金，10美金++num5--;num10++;}else { //20美金if (num10) { //优先给一张10美金和一张5美金num10--;num5--;} else { //不够的话就用3张5美金num5 -= 3;}}if (num5 < 0) return false;  //5美金不够}return true;}};

---

四、406.根据身高重建队列

题目链接
文章讲解
视频讲解

思路：
跟135. 分发糖果 一样，本题也需要考虑两个情况，身高和排在前面的人数。
那么先试试，先按其中一个元素来排序。

1. 如果按照k来从小到大排序，排完之后，会发现k的排列并不符合条件，身高也不符合条件，两个维度哪一个都没确定下来。
2. 如果按身高h来排序，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。
3. 那么此时优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。
   

vector版

代码如下：

class Solution {
public://people[i] = [hi, ki]//按身高从高到低排列，身高相等时，k值小的排前面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>> result;for (int i = 0; i < people.size(); i++) {int pos = people[i][1]; //获取people[i]的k值result.insert(result.begin() + pos, people[i]); //按照k值插入到结果集中}return result;}
};

list版

因为vector是动态数组，在插入的时候会触发扩容，且数组的插入效率低。而list底层是链表，插入的效率高得多。
但是需要注意的是vector是连续内存，所以可以用vector.begin()+pos的方式直接插入。
而链表不是连续内存，所以只能通过迭代器it++的形式找到要插入的位置再调用insert插入。

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);list<vector<int>> result; //list底层是链表实现，插入效率比vector高得多for (int i = 0; i < people.size(); i++) {int pos = people[i][1];auto it = result.begin(); //list<vector<int>> iterator it = result.begin();while (pos--) { //寻找插入位置it++;}result.insert(it, people[i]);}    return vector<vector<int>>(result.begin(), result.end());}
};

---

总结

贪心算法第三天，当遇到需要考虑两个维度的条件时，先处理好其中一个条件，再处理另一个条件。

明天继续加油！