java算法第34天 | 贪心算法 part03 ● 1005.K次取反后最大化的数组和 ● 134. 加油站 ● 135. 分发糖果

本文主要是介绍java算法第34天 | 贪心算法 part03 ● 1005.K次取反后最大化的数组和 ● 134. 加油站 ● 135. 分发糖果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

在这里插入图片描述

思路： 先将数组元素从小到大排列，从左向右处理，分两种情况讨论

当遇到负数，将负数变为正数，继续处理下一个元素
当遇到正数，对数组重排，循环处理当前的最小元素。
但需要注意的是，需要对count取模，因为k可能大于数组的长度。

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {  Arrays.sort(nums); //首先对数组从小到大排序int index=0;//记录当前处理的元素的下标int count=0; //记录处理的次数int len=nums.length;//用来做取模操作，防止k>len而出现内存泄露    while(count<k){//循环条件，总处理次数小于kif(nums[index % len]<0){//第一种情况：遇到负数，直接改变符号，继续处理下一个元素nums[index % len]=-nums[index % len];index++;count++;}else{//第二种情况：遇到正数，说明当前数组中已经全部是正数，需要重新排列，对最小元素做处理Arrays.sort(nums); index=0;while(count<k){//始终改变最小元素的符号nums[index % len]=-nums[index % len];count++;}}}return Arrays.stream(nums).sum();}
}

时间复杂度： $O (n l o g n)$
空间复杂度： $O (1)$

134. 加油站

在这里插入图片描述

思路： 首先，经过分析，这道题默认有一个条件就是：只要所有的油量供给减去所有的油量消耗大于等于0，则说明一定有解。
所以我们只需从0开始，计算gas[i]-cost[i]的累加和，如果和小于0，则继续从i+1开始计算和（这是因为只要和小于0，说明0到i之间没有可以作为起始点的位置，可以由反证法得出）。

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int totalSum=0;int sum=0;int start=0;for(int i=0;i<gas.length;i++){totalSum+=(gas[i]-cost[i]);sum+=(gas[i]-cost[i]);if(sum<0){start=i+1;sum=0;}}if(totalSum<0) return -1;else return start;}
}

时间复杂度：O(n)
空间复杂度：O(1)

135. 分发糖果

在这里插入图片描述

思路： 本题思路是两轮处理，第一轮从1开始，由左向右遍历，如果当前数据大于左侧数据，则当前数据在左侧数据基础上加1，否则赋值为1。第二轮从右向左遍历（从len-2开始），如果当前数据大于其右侧数据，则当前数据取max（右侧数据基础上加1，当前数据原始值）。

class Solution {public int candy(int[] ratings) {int len=ratings.length;int[] candy=new int[len];candy[0]=1;for(int i=1;i<len;i++){//判断右侧是否比左侧大if(ratings[i]>ratings[i-1])candy[i]=candy[i-1]+1;else{candy[i]=1;}}for(int i=len-2;i>=0;i--){//判断左侧是否比右侧大if(ratings[i]>ratings[i+1]) candy[i]=Math.max(candy[i+1]+1,candy[i]);}return Arrays.stream(candy).sum();}
}