力扣刷题[特殊字符]

加油站【贪心】

link

// 贪心
// 首先检查第 0 个加油站，并试图判断能否环绕一周；如果不能，就从第一个无法到达的加油站开始继续检查。
// 可以只从第一个加油站遍历一圈即可，对于中间有量可以出现负数的情况，可以假设为出发前向别人借的，走完一圈为正即可（换上之前借的）class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int ans = 0, min_s = 0, s = 0;  // s 表示油量，min_s 表示最小油量for (int i = 0; i < gas.size(); i++) {s += gas[i] - cost[i]; // 在 i 处加油，然后从 i 到 i+1if (s < min_s) {min_s = s; // 更新最小油量ans = i + 1; // 注意 s 减去 cost[i] 之后，汽车在 i+1 而不是 i}}// 循环结束后，s 即为 gas 之和减去 cost 之和return s < 0 ? -1 : ans;}
};

分发糖果【贪心】
link

从前往后遍历一遍，先确定右边评分大于左边的情况
再从后向前遍历，确定左孩子大于右孩子的情况

class Solution {
public:int candy(vector<int>& ratings) {vector<int> nums(ratings.size(), 1);for(int i = 1; i < ratings.size(); i++){if(ratings[i] > ratings[i-1]){nums[i] = nums[i-1] + 1;}}for(int i = ratings.size()-2; i>=0; i--){if(ratings[i] > ratings[i+1]){nums[i] = max(nums[i], nums[i+1]+1);}}int res = 0;for(int i = 0; i < nums.size();i++){res += nums[i];}return res;}
};