Day34 贪心 part03
1005.K次取反后最大化的数组和
我的思路：
又需要考虑最大值，首先将数组进行排序，将数字中所有<0的全部取反，如果此时k还要剩余，剩余偶数的话，可以反复对数组其中一个数字取反，最终数组仍然不变；剩余奇数，只需要再排序，对第一个元素取反一次
解答：
class Solution {public int largestSumAfterKNegations(int[] nums, int k) {Arrays.sort(nums);int i = 0;while(k > 0 && i < nums.length && nums[i] < 0) {nums[i] = -nums[i];k --;i ++;}if(k%2 != 0) {Arrays.sort(nums);nums[0] = -nums[0];}return Arrays.stream(nums).sum();}
}
134. 加油站
我的思路:
没想到如何用贪心思想
对着题解理解，只要gas比cost大，就能找到起始位置；而这个起始位置，只要索引 i 位置上gas < cost，就不断后移更新
解答：
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int total = 0;int cur = 0;int startIndex = 0;for(int i = 0; i < gas.length; i++) {int diff = gas[i] - cost[i];total += diff;cur += diff;if(cur < 0) {cur = 0;startIndex = i + 1;}}if(total < 0) {return -1;}return startIndex;}
}
135. 分发糖果
我的思路：
理解了题解
首先初始化candy为1，先从前往后遍历，如果rating后一个值大于前一个值，candy数 + 1；接着从后往前遍历，如果rating大于后一个值，比较自身candy数和后一个candy + 1，取较大值
解答:
class Solution {public int candy(int[] ratings) {int n = ratings.length;int[] candy = new int[n];Arrays.fill(candy, 1);for(int i = 1; i < n; i ++) {if(ratings[i] > ratings[i-1]) {candy[i] = candy[i-1] + 1;}}for(int i = n-2; i >= 0; i--) {if(ratings[i] > ratings[i+1]) {candy[i] = Math.max(candy[i], candy[i+1] + 1);}}int sum = Arrays.stream(candy).sum();return sum;}
}
