代码随想录算法【Day29】
Day29
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 += gas[index] - cost[index];
index = (index + 1) % cost.size();
}
if(rest >= 0 && index == i) return i;
}
return -1;
}
};
贪心法
局部最优可以推出全局最优
首先，总油量减去总消耗大于等于零那么一定可以跑完一圈，如果小于0则返回无解，代码中的totalSum反映了这一点。
设每个加油站的剩余量rest[i] = gas[i] - cost[i]
然后将rest[i]的累加记为curSum，如果curSum<0，说明[0,i]区间都不能作为起始位置，将起始位置更新为i+1
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. 分发糖果
两次贪心的策略：
-
一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
-
一次是从右到左遍历，只比较左边孩子评分比右边大的情况。
思考
1.为什么左孩子大于右孩子的情况一定要从后向前遍历，而右孩子大于左孩子的情况一定要从前往后遍历。
2.我们先完成从左往右遍历，然后在从右往左遍历的过程中，candyVec[i]就有两个选择，一个是右边的糖果数+1，即candyVec[i + 1] + 1，另一个是刚刚从左到右遍历的时候确定的自身的结果candyVec[i]。这时，candyVec[i]到底该选择多少作为最终的结果
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 result = 0;
for(int i = 0; i < candyVec.size(); i++)
result += candyVec[i];
return result;
}
};
860.柠檬水找零
这道题我认为它更倾向于模拟题
只需要维护三种金额的数量，5，10和20。
有如下三种情况：
-
情况一：账单是5，直接收下。
-
情况二：账单是10，消耗一个5，增加一个10
-
情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5
代码如下：
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;
ten++;
five--;
}
//情况三
if(bill == 20){
//优先找钱一张10和一张5
if(five > 0 && ten > 0){
five --;
ten --;
twenty ++;
}
else if(five >= 3){
five -= 3;
twenty ++;
}
else return false;
}
}
return true;
}
};
406.根据身高重建队列
总结
此题有两个维度，和135.分发糖果有点类似
在做这类题目时，一定要先确定一个维度，再确定另一个维度
若把两个维度一起考虑，一定会顾此失彼
思路
这道题我们应该确定身高这一个维度，按照身高从大到小排好序后，优先按身高高的people的k来插入，后序插入节点不会影响前面已经插入的节点
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;
}
};
代码解析：
