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

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

题目链接：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
思路：只要K大于0就把绝对值最大的负数依次变成正数，但是设计到正负数边界时，单纯的从小到大要考虑的排序因素很多。而如果一开始就采用按照绝对值从大到小排序，把负数变正数的操作完还有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();int sum = 0;for (int i = 0; i < nums.length; i++) {if (k > 0 && nums[i] < 0) {nums[i] = -nums[i];k--;}}if (k % 2 == 1) {nums[nums.length-1] = - nums[nums.length-1];}return Arrays.stream(nums).sum();}
}

二、134. 加油站

题目链接：https://leetcode.cn/problems/gas-station/
思路：我这是寻找第一个剩余值大于0 的点开始尝试计算，不行就再继续找，但是比较慢。换另外一种思路，gos和>cost和，那就一定可以跑完，那么只需要找到第一个累加和大于0的位置开始即可。

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int index = 0, sum = 0;boolean flag = true;for (int i = 0; i < gas.length; i++) {if (gas[i] >= cost[i] && flag) {flag = false;index = i;sum += gas[i] - cost[i];}else if (sum + gas[i] >= cost[i]) {sum += gas[i] - cost[i];}else {sum = 0;flag = true;}}sum = 0;for (int i = index; i < gas.length; i++) {sum += gas[i] - cost[i];if (sum < 0) return -1;}for (int i = 0; i <= index; i++) {sum += gas[i] - cost[i];if (sum < 0) return -1;}return index;}
}

三、135. 分发糖果

题目链接：https://leetcode.cn/problems/candy/
思路：从左右两边考虑。

class Solution {public int candy(int[] ratings) {int count = 0;int[] nums = new int[ratings.length];nums[0] = 1;for (int i = 1; i < ratings.length; i++) {if (ratings[i] > ratings[i-1]) {nums[i] = nums[i-1] + 1;}else {nums[i] = 1;}}for (int i = ratings.length-2; i >= 0; i--) {if (ratings[i] > ratings[i+1]) {nums[i] = Math.max(nums[i], nums[i+1] + 1);}}for (int num : nums) {count += num;}return count;}
}