1005.K次取反后最大化的数组和
1005. K 次取反后最大化的数组和 - 力扣(LeetCode)
秒了
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
Arrays.sort(nums);
// -4 -3 -2 -1 5
//-2 -2 0 2 5
int last = -1;
for(int i = 0;i if(k==0) break; if(nums[i]<0){ k--; nums[i]=-nums[i]; continue; } if(nums[i]>=0){ break; } } Arrays.sort(nums); if(k%2==1) nums[0]*=-1; // while(k-->0){ // nums[0] = - nums[0]; // } int res = 0; for(int i = 0;i res += nums[i]; } return res; } } 134. 加油站 134. 加油站 - 力扣(LeetCode) 这个图,就是假设curSum之前选择,有可能让这个curSum>0的话, 那么假设中间开始, 从最左到最右已经确定和小于0,假设从中间到最右,和大于0 那么总体小于0,那么区间1就是<0,,这个节点就不能用了。要更新。 所以:一遇到累加和curSum<0.区间start==i+1就可以了,curSum重新归0, 至于环的问题,total排除掉了没有结果的案例,也就是说,一定是有结果的 那么curSum之前没有结果,那么一定再后面,也就不需要环了 class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int curSum = 0; int totalSum = 0; int start = 0; for(int i = 0;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. 分发糖果 135. 分发糖果 - 力扣(LeetCode) 涉及到一个思想,就是想处理好一边再处理另一边,不要两边想着一起兼顾 第二次遍历的时候注意取最大值就可以了 class Solution { public int candy(int[] ratings) { int [] nums = new int[ratings.length]; for(int i = 0;i if(i==0){ nums[i]=1; } if(i>0&&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+1]+1,nums[i]); }else{ // nums[i] = Math.max(1,nums[i]); //不要这个else也可以 } } int res = 0; for(int i = 0;i res+=nums[i]; } return res; } } 推荐文章
发表评论