本文主要是介绍代码随想录算法训练营第三十三天｜1005.K次取反后最大化的数组和 134. 加油站 135. 分发糖果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1005.K次取反后最大化的数组和
链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
细节：
1. 首先这道题就可以想到用排序，因为排序是题目中没提的，而且又是数组
2. 个人根据数学思维就想到用绝对值进行排序，至于怎么排？
1、遍历数组，如果是负数，就进行翻转
2、翻转完负数之后，还有剩余的k
1、如果剩下的k是偶数，就可以直接相加了
2、如果剩下的k是奇数，数组的最后一个数组就是最小的数字，直接翻转就可以3. 绝对值想是好想，但是实际上有点难做，那就不妨再思考一下：
排序后再进行翻转
1、负数比k多，这种直接翻转就可以
2、负数翻转完了还有k
1、如果剩下的k是偶数，就不用在反转了
2、如果是奇数，那就需要翻转目前数组中最小的数
为了避免这种情况，需要在遍历数组的途中，不断收集翻转之后最小数字
class Solution {public int largestSumAfterKNegations(int[] nums, int k) {Arrays.sort(nums);int sum = 0;for (int i = 0; i < nums.length; i++){if (nums[i] < 0 && k > 0){nums[i] = -nums[i];k--;}}if (k % 2 == 1){Arrays.sort(nums);nums[0] = -nums[0];}for (int num : nums){sum += num;}return sum;}
}绝对值
class Solution {public int largestSumAfterKNegations(int[] nums, int k) {int sum = 0;// 将数组按照绝对值从大到小进行排序nums = IntStream.of(nums).boxed().sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1)).mapToInt(Integer::intValue).toArray();int len = nums.length;for (int i = 0; i < len; i++) {if (nums[i] < 0 && k > 0) {nums[i] = -nums[i];k--;}}System.out.println(k);if (k % 2 == 1) nums[len - 1] = -nums[len - 1];for (int num : nums) {sum += num;}return sum;}
}134. 加油站
链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
细节：
1. 首先我是从题目中的例子就反应过来，是不是可以把加油站加总和，油耗加总和，然后再相减？
2. 通过记录这个相减去感觉能不能跑一圈，这时看了看代码随想录
如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
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 totalSum = 0;int index = 0;for (int i = 0; i < gas.length; i++) {curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if (curSum < 0) {index = i + 1 ; curSum = 0;}}if (totalSum < 0) return -1;return index;}
}135. 分发糖果
链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
细节：
1. Hard题选择性放弃
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;}
}这篇关于代码随想录算法训练营第三十三天｜1005.K次取反后最大化的数组和 134. 加油站 135. 分发糖果的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
