文章目录 LeetCode 134. 加油站思路AC代码 LeetCode135. 分发糖果思路AC代码 LeetCode 1005.K次取反后最大化的数组和思路AC代码总结

LeetCode 134. 加油站 思路

两个数组一个是 增加汽油量 gas[ ] 一个耗费汽油量 cost[ ]

可以换一个思路，首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。

每个加油站的剩余量rest[i]为gas[i] - cost[i]。

i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。

这道题的局部最优就是： 当前累加rest[j]的和cerSum一旦小于0，起始位置就要j+1,因为从j开始一定不行全局最优就是找到可以跑一圈的位置

AC代码 class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int cursum=0; int totalsum=0; int index=0; for(int i=0;i<gas.length;i++) { cursum+= gas[i]-cost[i]; totalsum+= gas[i]- cost[i]; if( cursum<0) { index=i+1; cursum=0; } } if(totalsum<0) return -1; return index; } } LeetCode135. 分发糖果 思路

要满足两个规则

每个孩子至少分配到 1 个糖果相邻的孩子中，评分高的孩子必须获得更多的糖果。 我们需要从 左边 和右边两个方面来思考问题 从而判断孩子的相邻 ，左和右 如果 孩子分数大于周边 他的苹果还要+1 如图所示 AC代码 class Solution { public int candy(int[] ratings) { int[]Can= new int[ratings.length]; int len= ratings.length; Can[0]=1; for(int i=1;i<len;i++) { Can[i]= ratings[i]>ratings[i-1]? Can[i-1]+1:1; } for( int i=len-2;i>=0;i--) { if(ratings[i]>ratings[i+1]) { Can[i]=Math.max(Can[i],Can[i+1]+1); } } int ans=0; for( int num: Can) { ans+= num; } return ans; } } LeetCode 1005.K次取反后最大化的数组和 思路

首先我们将题理解一下 就是在k的 有限次数下， 完成对于数字的取反， 所以第一步要将所有的负数都取反， 第二步在找绝对值最小的正数将其取反，就算变成了负数也对最终的sum影响不大因为是最小的负数

1 排序 Arrays.sort(nums);2 将负数都转成整数3 寻找绝对值最小的数字4 如果是k是奇数 再将其进行取反 AC代码 class Solution { public int largestSumAfterKNegations(int[] nums, int k) { // 先排序 Arrays.sort(nums); // 再将负数都转成整数 int index=0; int len = nums.length; for(int i =0;i<len-1;i++) { if( nums[index]<0&& k>0) { nums[index]= -nums[index]; k--; if( nums[index]>=Math.abs(nums[index+1])) { index++; } } } if( k%2==1) { nums[index]= -nums[index]; } // 找绝对值最小的 // 如果K是奇数 return Arrays.stream(nums).sum(); } } 总结

今天第一次刷到困难难度的题 ， 在沉默中努力，在机会中爆发

---

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，会注明原创字样,如未注明都非原创，如有侵权请联系删除！；3.作者投稿可能会经我们编辑修改或补充；4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。