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

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

public class Solution {public int LargestSumAfterKNegations(int[] nums, int k) {int cnt=0;int sum=0;int min=int.MaxValue;Array.Sort(nums);for(int i=0;i<nums.Length;i++){if(nums[i]>=0){continue;}else{nums[i]=-nums[i];cnt++;}if(cnt==k){for(int j=0;j<nums.Length;j++){sum+=nums[j];}return  sum;}}for(int i=0;i<nums.Length;i++){if(nums[i]<min){min=nums[i];}}k-=cnt;if(k%2==0){for(int j=0;j<nums.Length;j++){sum+=nums[j];}return  sum;}if(k%2==1){for(int j=0;j<nums.Length;j++){sum+=nums[j];}return  sum-2*min;}return sum;}
}

先排序，每次都找到最小的数然后反转，然后计数如果所有负数反转完成之前达到K直接求和，如果K有多余了就去反复反转最小的，然后求和就行。

134.加油站

public class Solution {public int CanCompleteCircuit(int[] gas, int[] cost) {int cursum=0;int totalsum=0;int start=0;int sum=0;for(int i=0;i<gas.Length;i++){cursum+=gas[i]-cost[i];totalsum+=gas[i]-cost[i];if(cursum<0){start=i+1;cursum=0;}}if(totalsum<0){return -1;}return start;
}
}

 135.分发糖果

public class Solution {public int Candy(int[] ratings) {int[]can=new int[ratings.Length];int sum=0;for(int i=0;i<can.Length;i++){can[i]=1;}for(int i=1;i<ratings.Length;i++){if(ratings[i]>ratings[i-1]){can[i]=can[i-1]+1;}}for(int i=ratings.Length-2;i>=0;i--){if(ratings[i]>ratings[i+1]){can[i]=Math.Max(can[i+1]+1,can[i]);}}for(int i=0;i<can.Length;i++){sum+=can[i];}return sum;}
}

进行两遍，先是从左到右考虑右边比左边大的时候，右边就是左边的值加1，然后最后从右到左如果左边比右边大就比较右边加1和当前的值比，哪个大取哪个，最后求和返回就行。