134. 加油站
文档讲解:代码随想录.加油站
视频讲解:贪心算法,得这么加油才能跑完全程!LeetCode :134.加油站
状态:已完成
代码实现
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int target_sum = 0;
int cur_sum = 0;
int begin = 0;
for (int i = 0; i < gas.size(); i++) {
cur_sum += gas[i] - cost[i]; // 这里是累加的思路
target_sum += gas[i] - cost[i];
if (cur_sum < 0) {
begin = i + 1;
cur_sum = 0;
}
}
if (target_sum < 0) {
return -1;
}
return begin;
}
};
心得体会
- 需要仔细查看题目中的条件
135. 分发糖果
文档讲解:代码随想录.分发糖果
视频讲解:贪心算法,两者兼顾很容易顾此失彼!LeetCode:135.分发糖果
状态:已完成
代码实现
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> candy_vec(ratings.size(), 1);
for (int i = 1; i < ratings.size(); i++) {
if (ratings[i] > ratings[i - 1]) {
candy_vec[i] = candy_vec[i - 1] + 1;
}
}
for (int i = ratings.size() - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candy_vec[i] = max(candy_vec[i], candy_vec[i + 1] + 1);
}
}
int result = 0;
for (int i = 0; i < candy_vec.size(); i++) {
result += candy_vec[i];
}
return result;
}
};
心得体会
- 采用了两次贪心
一次是从左到右遍历,只比较右边孩子评分比左边大的情况。
一次是从右到左遍历,只比较左边孩子评分比右边大的情况。
这样从局部最优推出了全局最优,即:相邻的孩子中,评分高的孩子获得更多的糖果。
860.柠檬水找零
文档讲解:代码随想录.柠檬水找零
视频讲解:贪心算法,看上去复杂,其实逻辑都是固定的!
状态:已完成
代码实现
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;
}
five--;
ten++;
}
if (bill == 20) {
if (ten > 0 && five > 0) {
ten--;
five--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
}
return true;
}
};
心得体会
- 实际上仔细分析所有的可能,可以直接实现
406.根据身高重建队列
文档讲解:代码随想录.根据身高重建队列
视频讲解:贪心算法,不要两边一起贪,会顾此失彼 | LeetCode:406.根据身高重建队列
状态:已完成
代码实现
class Solution {
public:
static bool cmp(vector<int> a, 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;
}
};
心得体会
- 理解起来有点困难