代码随想录训练营Day33（贪心算法）：Leetcode1005、134、135（难得有一天能完全独立做出题目）

Leetcode1005:

题目描述：

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

• 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

代码及注释:

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {//使用优先队列存储值最小的K个元素priority_queue<pair<int, int>>p;for (int i = 0; i < nums.size(); i++) {//存储值最小，因为默认是大根堆，所以存储负值p.push(pair<int, int>(-nums[i], i));}//对值最小的值取反//1.如果存在负数，优先取反最小的负数，可以使得和变大//2.不存在负数，但有0值，取反0值可以让数组值和不变//3.只存在非负整数，取反最小的值，可以使得代价最小//执行k次while (!p.empty() && k--) {pair<int, int>pp = p.top();p.pop();//如果只有0和正整数，可以对0取反k次，因此可以直接跳出循环if (nums[pp.second] == 0)break;else nums[pp.second] = -nums[pp.second];pp.first = -pp.first;//完成取反，得到新的值，重新加入p.push(pp);}int sum = 0;for (int i = 0; i < nums.size(); i++) {sum += nums[i];}return sum;}
};

Leetcode134:

题目描述：

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

代码及注释:

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size();//处理后的gas代表，gas[i]从第i个加油站到达第(i+1)个加油站所增加/减少的油for (int i = 0; i < n; i++) {gas[i] -= cost[i];}//由于起点唯一，因此如果存在等于0可以做起点，那只可能是只有一个元素if (n == 1 && gas[0] >= 0)return 0;//对每个加油站都尝试作为起点for (int i = 0; i < n;) {//作为起点的加油站必须能到达下一个加油站，本来就是没有油//gas[i]为负数，就不可能可以让i作为起点//大于0才能作为起点if (gas[i] > 0) {//记录到达加油站i+1还剩多少油int sum = gas[i];int begin = i;//>=0 才能说明可以到达 i+1while (sum >= 0) {//继续向后走i = (i + 1) % n;sum += gas[i];//直到又回到起点，完成搜索if (sum >= 0 && i == begin)return begin;}//剪枝if (i > begin && i < n)continue;i = begin + 1;}else {i++;}}return -1;}
};

Leetcode135:

题目描述：

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

代码及注释:

class Solution {
public:int candy(vector<int>& ratings) {int n = ratings.size();int* ans = new int[n];//第一个孩子先给一个糖果ans[0] = 1;//边走边发糖果for (int i = 1; i < n; i++) {//如果当前孩子评分>前一个孩子if (ratings[i] > ratings[i - 1]) {//比前一个孩子多发一个糖果即可ans[i] = ans[i - 1] + 1;}//如果<=前一个孩子评分else {//给一个糖果就行ans[i] = 1;int j = i - 1;//前一个孩子也是只有一个糖果&&前一个孩子评分>当前孩子评分if (ans[j] == 1 && ratings[j] > ratings[i]) {//i-1孩子多发一个糖果ans[j] += 1;j--;//往前走，回溯while (j >= 0 && ratings[j] > ratings[j + 1] && ans[j] <= ans[j + 1])ans[j] = ans[j + 1] + 1, j--;}}}int sum = 0;for (int i = 0; i < n; i++) {sum += ans[i];}return sum;}
};