代码随想录day29贪心算法3

134. 加油站

题目链接
文章讲解

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {// 初始化变量：start表示起始加油站的索引，cur表示当前油量，sum表示油量的总和int start = 0, cur = 0, sum = 0;// 遍历整个加油站for (int i = 0; i < gas.size(); i++) {// 计算从当前位置出发时的油量sum += gas[i] - cost[i];  // 记录总的油量变化cur += gas[i] - cost[i];  // 记录从当前起始点的油量变化// 如果当前油量小于0，说明无法从当前起点出发，重新设置起始点if (cur < 0) {start = i + 1;  // 从下一个加油站开始尝试cur = 0;  // 油量清零}}// 如果总的油量变化小于0，说明无法完成一圈if (sum < 0) return -1;// 返回可以完成一圈的起始加油站的索引return start;}
};

135. 分发糖果

题目链接
文章讲解

class Solution {
public:int candy(vector<int>& ratings) {const int N = 1e5 + 10;  // 假定足够大的数组大小int a[N];  fill(a, a + N, 1);for (int i = 0; i < ratings.size() - 1; i++) {if (ratings[i + 1] > ratings[i]) {a[i + 1]=a[i]+1;  // 右边学生评分更高，糖果数量加 1}}// 从右到左遍历，如果左边的学生评分高于右边的学生，增加左边学生的糖果数量for (int i = ratings.size() - 1; i >= 1; i--) {if (ratings[i - 1] > ratings[i]) {a[i - 1] = max(a[i - 1], a[i] + 1);  // 保证左边学生的糖果数量比右边更多}}int ans=0;for(int i=0;i<ratings.size();i++){ans+=a[i];}return ans;}
};

860.柠檬水找零

题目链接
文章讲解

class Solution {
public:bool lemonadeChange(vector<int>& bills) {const int N = 1e5 + 10;  // 假定足够大的数组大小int a[N];  // 用数组 a 来记录 5、10、20 面额的钞票数量memset(a, 0, sizeof(a));  // 初始化所有面额的钞票数量为 0// 遍历每个顾客支付的金额for (int i = 0; i < bills.size(); i++) {// 如果顾客支付的是 5 元钞票，增加 5 元的钞票数量if (bills[i] == 5) a[5]++;// 如果顾客支付的是 10 元钞票if (bills[i] == 10) {a[10]++;  // 增加 10 元的钞票数量a[5]--;   // 减少 5 元的钞票数量用于找零// 如果 5 元钞票数量不足，返回 false，表示找零失败if (a[5] < 0) return false;}// 如果顾客支付的是 20 元钞票if (bills[i] == 20) {// 首先尝试找 10 元加 5 元作为找零if (a[10] > 0) {a[10]--;  // 减少 10 元的钞票a[5]--;   // 减少 5 元的钞票} else {// 否则只能找 5 元钞票，找 3 张 5 元钞票a[5] -= 3;}// 如果 5 元钞票数量不足，返回 false，表示找零失败if (a[5] < 0) return false;}}// 如果所有顾客都能顺利得到找零，返回 truereturn true;}
};

406.根据身高重建队列

题目链接
文章讲解

class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {// 如果身高相同，按 position 升序排列；否则按身高降序排列if(a[0] == b[0]) return a[1] < b[1];return a[0] > b[0];  // 高度大的排前面}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {// 排序：先按身高降序，再按 position 升序sort(people.begin(), people.end(), cmp);vector<vector<int>> q;// 插入每个人到正确的位置for (int i = 0; i < people.size(); i++) {int p = people[i][1];  // 当前位置q.insert(q.begin() + p, people[i]);  // 在指定位置插入}return q;}
};