「代码随想录算法训练营」第二十五天 | 贪心算法 part3
134. 加油站
题目链接:https://leetcode.cn/problems/gas-station/
题目难度:中等
文章讲解:https://programmercarl.com/0134.加油站.html
视频讲解:https://www.bilibili.com/video/BV1jA411r7WX
题目状态:没有思路,学习题解
思路一:全局最优解
首先将所有路径的加油量和耗油量加一起,看是否大于0,若小于0,表示整体的加油量小于耗油量,不可能跑完全程,直接返回-1;若大于0,看其到每一站存储的油量最小值是否大于等于0,若是,则表示其在每一站都是可以跑完的,直接返回0(表示从0开始出发可以完成全程);若并不是这样的,则反向加出发点,看其什么时候的最小值不会为负数,此时就是出发点的位置。
代码一:
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int curSum = 0;
int min = INT_MAX;
for(int i = 0; i < gas.size(); ++i) {
int rest = gas[i] - cost[i];
curSum += rest;
min = std::min(min, curSum);
}
if(curSum < 0) return -1;
if(min >= 0) return 0;
for(int i = gas.size() - 1; i >= 0; --i) {
int rest = gas[i] - cost[i];
min += rest;
if(min >= 0) return i;
}
return -1;
}
};
思路二:贪心算法
局部最优,首先当所有路径的油差之和小于0,直接返回-1,其不可能跑完全程;再次,若从A点到B点的油差和小于0,要从B点的下一点重新记录,因为A到B之间无论从哪一点开始,都跑不完,最后返回合适的位置。
代码:
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 < cost.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. 分发糖果
题目链接:https://leetcode.cn/problems/candy/
题目难度:困难
文章讲解:https://programmercarl.com/0135.分发糖果.html
视频讲解:https://www.bilibili.com/video/BV1ev4y1r7wN
题目状态:好难,要长脑子了
思路:
首先创建一个数组,存储每个孩子手里的糖。
- 首先,每个孩子手里都要有一颗糖。
- 从左向右,判断右边孩子分数是否要大于左边孩子,若大于,就把右边孩子手里加一颗糖。
- 从右向左,判断左边孩子的分数是否大于右边孩子,若大于,则判断左边孩子手里的糖是否已经大于右边孩子了,若不大于,则将左边孩子手里的糖加到比右边孩子大。
代码:
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> candyVal(ratings.size(), 1);
for(int i = 1; i < ratings.size(); ++i) {
if(ratings[i] > ratings[i - 1]) candyVal[i] = candyVal[i - 1] + 1;
}
for(int i = ratings.size() - 2; i >= 0; --i) {
if(ratings[i] > ratings[i + 1]) candyVal[i] = max(candyVal[i], candyVal[i + 1] + 1);
}
int res = 0;
for(auto &val : candyVal) res += val;
return res;
}
};
860. 柠檬水找零
题目链接:https://leetcode.cn/problems/lemonade-change/
题目难度:简单
文章讲解:https://programmercarl.com/0860.柠檬水找零.html
视频讲解:https://www.bilibili.com/video/BV12x4y1j7DD
题目状态:没绕过来,看完题解豁然开朗
思路:
维护五块钱和十块钱的个数five和ten
- 当给5元时,five++;
- 当给10元时,five--;
- 当给20元时,要么ten--和five--,要么five-3。
代码:
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0;
for(int i = 0; i < bills.size(); ++i) {
if(bills[i] == 5) five++;
if(bills[i] == 10) {
if(five <= 0) return false;
five--;
ten++;
}
if(bills[i] == 20) {
if(five > 0 && ten > 0) {
five--;
ten--;
} else if(five >= 3) {
five -= 3;
} else {
return false;
}
}
}
return true;
}
};
406. 根据身高重建队列
题目链接:https://leetcode.cn/problems/queue-reconstruction-by-height/
题目难度:中等
文章讲解:https://programmercarl.com/0406.根据身高重建队列.html
视频讲解:https://www.bilibili.com/video/BV1EA411675Y
题目状态:继续学习题解...
思路:
首先对整个数组进行排序,排序规则是比较身高,最高的排在前面,若身高相同,比较前方人数,人数低的排在前面。
之后开始插入返回数组,按照排序后的数组依次插入,插入的位置是自己的前方人数,下图更容易理解插入的过程。
代码实现:
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;
}
};
链表代码:(性能更好)
class Solution {
public:
// 身高从大到小排(身高相同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);
list<vector<int>> que; // list底层是链表实现,插入效率比vector高的多
for (int i = 0; i < people.size(); i++) {
int position = people[i][1]; // 插入到下标为position的位置
std::list<vector<int>>::iterator it = que.begin();
while (position--) { // 寻找在插入位置
it++;
}
que.insert(it, people[i]);
}
return vector<vector<int>>(que.begin(), que.end());
}
};
热门相关:我真不是暴发户 【戏说台湾】寿桃太子爷 功夫圣医 赠我深爱如长风 勇闯天涯