代码随想录算法训练营第三十三天|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和当前的值比,哪个大取哪个,最后求和返回就行。