代码随想录打卡Day29
今天的题目尊嘟好难…除了第三题没看视频，其他的题目都是看了视频才做出来的。二刷等我。
134. 加油站
感觉这道题和之前的53. 最大子序和有点像，最大子序和是一旦当前总和为负数则立即抛弃当前的总和，从下个位置重新开始计算，而这道题是一旦遇到当前剩余的燃油小于0，则立马抛弃当前的燃油总和，以下个位置为新起点，当然这道题还需要计算遍历过的所有节点的燃油与损耗之差，万一循环结束current_sum>=0，但是total_sum<0也是不行的，所以在循环结束以后并不是判断current_sum是否大于0，因为有可能出现从0出发到不了第i个节点，从第i + 1个节点遍历到结束时current_sum >= 0，但是剩下的燃油＋i节点前面的燃油坚持不到第i个节点的情况，综上，在循环结束以后应该判断total_sum是否大于等于0。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int result = 0; //记录起始位置
int current_sum = 0; //到达某个站点后剩余的油量
int total_sum = 0; //记录所有能得到的油与消耗量之间的差值
for(int i = 0; i < gas.size(); i++){
current_sum += (gas[i] - cost[i]); //执行完这条语句后车子已经到达第i + 1个站点了
total_sum += (gas[i] - cost[i]);
if(current_sum < 0){
result = i + 1;
current_sum = 0;
}
}
if(total_sum < 0) return -1; //已经遍历到末尾了，不可能跑一圈
return result;
}
};
135. 分发糖果
这道题我思路想到了，先从左往右遍历，处理一遍，再从后往前遍历一遍，再处理一遍，但是我在一些代码细节上没有想清楚，所以老是写不对，就很气。。。首先第一个代码细节是明确两次遍历的处理对象是谁，第一次从左往右遍历应该处理左边的值还是右边的值呢？我这里处理的是右边的值，代码是这么写的
//从左往右遍历(右边比左边大的情况)
for(int i = 1; i < ratings.size(); i++){
if(ratings[i] > ratings[i - 1])
v[i] = v[i - 1] + 1;
}
第二次遍历从右往左，由于前面遍历处理的是右值，反过来遍历的时候就必须处理左值，为什么？因为如果倒过来遍历还是处理右值的话，相当于做无用功，上一次遍历的时候已经对右值赋值过了，没有必要再用一次循环。处理左值的代码我是这么写的
//从右往左遍历(左边比右边大的情况)
for(int i = ratings.size() - 1; i > 0; i--){
if(ratings[i] < ratings[i - 1])
v[i - 1] = max(v[i] + 1, v[i - 1]);
}
第二个细节就是第二次遍历的时候的赋值操作，并不是简单地在旁边的较小值的糖果数上加1就完事了，有可能在第一次遍历的时候已经满足大小关系了，第二遍再处理一遍的话会导致重复处理，糖果一定会多发，所以一定要取赋值过后与之前的值之间的较大值。
这是完整的代码
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> v(ratings.size(), 1);
//从左往右遍历(右边比左边大的情况)
for(int i = 1; i < ratings.size(); i++){
if(ratings[i] > ratings[i - 1])
v[i] = v[i - 1] + 1;
}
//从右往左遍历(左边比右边大的情况)
for(int i = ratings.size() - 1; i > 0; i--){
if(ratings[i] < ratings[i - 1])
v[i - 1] = max(v[i] + 1, v[i - 1]);
}
return accumulate(v.begin(), v.end(), 0);
}
};
860.柠檬水找零
这个比较简单，收5块钱不找零，收10块钱只能找5块的零，收20块的优先用10+5找零，其次再用5+5+5找零，按照这个规则去遍历数组，在钞票数够用的情况下一定可以找零，return true，如果出现钞票不够的情况直接return false。
class Solution {
public:
map<int, int> money;
bool lemonadeChange(vector<int>& bills) {
for(int i = 0; i < bills.size(); i++){
if(bills[i] == 5)
money[5]++;
else if(bills[i] == 10){
if(money[5] == 0) //必须要有5元零钱
return false;
money[5]--;
money[10]++;
}
else{
if(money[5] == 0 || (money[10] * 10 + money[5] * 5 < 15)) //找不起钱
return false;
if(money[10] > 0){
money[10]--;
money[5]--;
}
else money[5] -= 3;
}
}
return true;
}
};
406.根据身高重建队列
说是说这个题目和分发糖果的思路很像，但是我还是做不出来┭┮﹏┭┮被自己菜哭了。这道题有两个维度，一个是身高h，一个是前面比本人高的人数k，这道题并不能先选择任意一个维度进行排序，因为先按照k排序过后得到的数组依旧没什么逻辑性，很混乱，但是按照身高降序排列的话能得到一些比较好的性质，那就是后面的元素插到前面时，该元素前面的元素的相对位置无需变动，因为从后面插进来的人身高一定会比前面的人矮，并不会影响前面的人的k值，这个性质就非常好。
这道题的原理想清楚以后还没有那么容易写出来，这个题目还比较考验C++基本功，需要对vector<vector>自定义排序规则，首先按身高进行降序排列，身高相同的则k值小的排前面。第二个就是要将元素插入到指定位置，其余元素相对位置不变，vector并没有现成的函数可以调用，所以要自己手搓一个，这里主要还是用swap函数来实现，当某个元素需要插入到前面时，就将该元素与前一个元素交换位置，如此循环，直到该元素被交换到指定位置。
class Solution {
public:
static bool compareVectors(const std::vector<int>& a, const std::vector<int>& b) {
// 按照身高降序排列,若身高相同则k值小的靠前
if(a[0] > b[0]) return true;
else if(a[0] < b[0]) return false;
else return a[1] < b[1];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), compareVectors);
for(int i = 0; i < people.size(); i++){
int j = i;
int target = people[i][1];
while(j > target){
iter_swap(people.begin() + j, people.begin() + j - 1);
j--;
}
}
return people;
}
};
好难啊。。今天这个博客是我写的篇幅最大的博客之一了。