【代码随想录训练营】【Day33休息】【Day34】第八章｜贪心算法｜1005.K次取反后最大化的数组和｜134. 加油站｜135. 分发糖果

K 次取反后最大化的数组和

题目详细：LeetCode.1005

这道题比较简单，这里直接给出贪心策略：

• 局部最优解：
  • 按照 负数 > 0 > 正数 的优先级次序，依次对nums中的较小数值进行取反
  • 因为负负得正，负值越小，其相反数越大
  • 如果值都为正数，那么则取较小的值进行取反，尽可能的最大化数组和
• 整体最优解：整体的数组和最大

Java解法（贪心，数组有序）：

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {// 对原数组进行排序Arrays.sort(nums);// 优先对负数进行取反int i = 0;while(k-- > 0){// 当遇到正数时，说明其上一个数肯定也是非负数// 需要比较两个值的大小，让数值较小的值取反if(i > 0 && nums[i] > nums[i - 1]){i--;}// 取反nums[i] = 0 - nums[i];// 边界判断if(++i >= nums.length)i = nums.length - 1;}// 累计数组总和int sum = 0;for(int n: nums){sum += n;}return sum;}
}

当然由于LeetCode给出的数据样本，范围较小且保证样本数组都落在一定范围内，我们也可以利用数组下标来映射nums中的数值，使数值在映射数组中得到有序，就不用Arrays.sort方法了。

Java解法（贪心，数组不有序）：

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {// 样本数据都满足，-100 <= nums[i] <= 100，这个范围的大小是201int[] number = new int[201];// 数组下标[-100,100]表示数值大小，元素值表示数值的个数for (int t : nums) {// 利用 t + 100 将[-100,100]映射到[0,200]上number[t + 100]++;}int i = 0;while (k-- > 0) {// 跳过记录次数为0的数字，找到当前nums中最小的数字while (number[i] == 0){i++;}// 若 i > 100，说明索引到了正数if (i > 100) {if(k % 2 == 0){// 正数取偶数次反，依旧是正数，直接break跳出循环；break;}// 正数取奇数次反，一定是负数，直接k = 0，后续执行一次数值取反就行k = 0;}// 取反number[i]--;// 该数字的个数 - 1number[200 - i]++;// 该数字的相反数个数 + 1}// 累计数字个数求和int sum = 0;for (int j = 0; j < number.length ; j++) {// j - 100 是数字的大小，number[j]是该数字出现次数.sum += (j - 100)* number[j];}return sum;}
}

---

加油站

题目详细：LeetCode.134

这道题一开始我的思路是比较正确的：

• 假如我们从某一个加油站开始，那么这个加油站之前和之后的路段都是它要行驶的路段
• 所以判断能否行驶一周，那么只需要累计每一段路程的差值，如果差值不为负，说明能够行驶一周，否则无法行驶一周，返回 -1
• 那么再根据我的贪心的思想，我计算并记录了每一段路程中，差值为正且最大的加油站开始，觉得这样就可以满足后续的路程
• 最后根据累计值，判断能否行驶一周，如果可以则返回记录的下标

但是经过测试后，发现还是会有错误的数据样本，看完题解之后，才发现我的思路是比较片面的，主要的原因在于确定起始坐标上犯了迷糊，若当前的累计值cur_sum < 0，起始位置至少要是i+1，而不是i

所以正确的贪心策略应该是：

• 局部最优解：
  • 当前累加rest[i]的和cur_sum < 0时，起始位置start_index至少要更新到i+1
  • 因为假如从i之前开始，那么它走到第i个时，必定是cur_sum < 0，就无法继续行驶了
• 整体最优解：找到可以跑一圈的起始位置start_index，如果最后所有油耗的累计值 < 0，说明车辆不足油跑一圈，返回 -1

这里我定义了一个变量min_sum，来记录路程中差值最大的油耗，只要当cur_sum < min_sum时，就需要更新start_index = i + 1。

Java解法（贪心）：

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int n = gas.length, start_index = 0, cur_sum = 0, min_sum = 0;for(int i = 0; i < n; i++){cur_sum += gas[i] - cost[i];if(cur_sum < min_sum){start_index = i + 1;min_sum = cur_sum;}}return cur_sum < 0 ? -1 : start_index;}
}

如果起始位置的更新条件为cur_sum < 0时，则需要更新cur_sum = 0，这是意义更加明确的解法，表示从车辆从当前加油站开始，其之前的加油站都还未经过，所以不需要累计油耗，重置cur_sum = 0，后续再累计油耗；

不过就需要定义一个变量total_sum，通过该变量来判断是否能够绕行一圈了。

Java解法（贪心）：

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int n = gas.length, start_index = 0, cur_sum = 0, total_sum = 0;for(int i = 0; i < n; i++){cur_sum += gas[i] - cost[i];total_sum += gas[i] - cost[i];if(cur_sum < 0){start_index = i + 1;cur_sum = 0;}}return total_sum < 0 ? -1 : start_index;}
}

---

分发糖果

题目详细：LeetCode.135

我一开始的分发策略是：

• 第一次是从左到右遍历，比较左边孩子和右边孩子的评分，如果左边孩子比右边孩子的评分高，那么左边孩子的糖果数量 = 右边孩子的糖果数量 + 1（第一次遍历，这样变成了左边孩子的糖果数量由右边孩子决定，但是右边孩子的糖果数量还未确定，进而在这一步就确定左边孩子的糖果数量是错误的）。
• 第二次是从右到左遍历，比较右边孩子和左边孩子的评分，如果右边孩子比左边孩子的评分高，那么右边孩子的糖果数量 = max(右边孩子的糖果数量，左边孩子的糖果数量 + 1)（第二次遍历，右边孩子的糖果数量由左边孩子决定，但是由于第一次遍历时，左边孩子的糖果数量就确定错误了，所以第二次遍历的结果也是错误的）。

做题的时候总觉得这样的思路没问题呀，怎么老是通过不了一些测试样本呢，看过题解之后才发现括号里那些没有发现的错误，详细的题解可查阅：《代码随想录》— 分发糖果

按我原来的分发策略举个错误的例子，例如：

• 因为rating[1]与rating[2]的比较，是要利用上rating[2]与rating[3]的比较结果来确定rating[2]的糖果数量，才能进而确定rating[1]的糖果数量
• 假如从前向后遍历，就无从得知rating[2]与rating[3]的的比较结果了，所以要从后向前遍历。

所以本题正确的分发策略应该是：

• 局部最优解：
  • 第一次是从左到右遍历，所以右边孩子的糖果数量都能通过左边孩子的糖果数量得到确定（右边孩子的糖果数量 = 左边孩子的糖果数量 + 1），只比较右边孩子比左边孩子的评分高的情况。
  • 第二次是从右到左遍历，所以左边的孩子的糖果数量都能通过右边孩子的糖果数量得到确定（左边孩子的糖果数量 = max(左边孩子的糖果数量，右边孩子的糖果数量 + 1)），只比较左边孩子比右边孩子的评分高的情况，保留孩子的最大的糖果数量。
• 整体最优解：相邻的孩子中，评分高的孩子获得更多的糖果。
• 最后累计所有孩子的糖果数量即可得到结果

Java解法（贪心）：

class Solution {public int candy(int[] ratings) {int len = ratings.length;int[] candy = new int[len];// 每个孩子至少分得1个糖果Arrays.fill(candy, 1);for(int i = 1; i < len; i++){if(ratings[i] > ratings[i - 1]){candy[i] = candy[i - 1] + 1;}}for(int i = len - 2; i >= 0; i--){if(ratings[i] > ratings[i + 1]){candy[i] = Math.max(candy[i], candy[i + 1] + 1);}}int sum = 0;for(int n: candy){sum += n;}return sum;}
}

---