代码随想录算法训练营第三十三天|1005. K 次取反后最大化的数组和、134. 加油站、135. 分发糖果。

本文主要是介绍代码随想录算法训练营第三十三天|1005. K 次取反后最大化的数组和、134. 加油站、135. 分发糖果。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

题目链接：K 次取反后最大化的数组和

题目描述：
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组可能的最大和。

解题思路：
本题很简单就是首先将负数变成正数，直到k为零，若k小于数组长度，应首先改变更小的负数，因此我们先将数组从小往大的排序，又因为若k大于数组长度，若k是偶数则可对称的变换不会导致数值改变，若k为奇数则要改变一个，这时改变最小的数即可，因此还要按照绝对值大小进行排序，所以综合下来，按照绝对值从大往小排序能满足这两个条件。

代码实现：

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {nums = IntStream.of(nums).boxed().sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1)).mapToInt(Integer::intValue).toArray();for (int i = 0; i < nums.length; i++) {if (nums[i] < 0 && k > 0) {nums[i] = -nums[i];k--;}}if (k % 2 == 1) {nums[nums.length - 1] = -nums[nums.length - 1];}return Arrays.stream(nums).sum();}
}

134. 加油站

题目链接：加油站

题目描述：
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯一的。

解题思路：
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。

代码实现：

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int curSum = 0;int Sum = 0;int index = 0;for (int i = 0; i < gas.length; i++) {curSum += gas[i] - cost[i];Sum += gas[i] - cost[i];if (curSum < 0) {index = (i + 1) % gas.length ; curSum = 0;}}if (Sum < 0) return -1;return index;}
}

135. 分发糖果

题目链接：分发糖果

题目描述：
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。

解题思路：
本题的关键点是要分别进行左右两边的比较，并且若比较左边则要从前往后比较，比较右边要从后往前比较，因为更改糖果数的时候要比右边多所以要用到右边的最终糖果数。

代码实现：

class Solution {/**分两个阶段1、起点下标1 从左往右，只要 右边 比 左边 大，右边的糖果=左边 + 12、起点下标 ratings.length - 2 从右往左， 只要左边 比 右边 大，此时 左边的糖果应该 取本身的糖果数（符合比它左边大） 和 右边糖果数 + 1 二者的最大值，这样才符合 它比它左边的大，也比它右边大*/public int candy(int[] ratings) {int len = ratings.length;int[] candyVec = new int[len];candyVec[0] = 1;//从前往后遍历for (int i = 1; i < len; i++) {candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;}//从后往前遍历for (int i = len - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);}}int ans = 0;for (int num : candyVec) {ans += num;}return ans;}
}