赞
踩
我的思路:
又需要考虑最大值,首先将数组进行排序,将数字中所有<0的全部取反,如果此时k还要剩余,剩余偶数的话,可以反复对数组其中一个数字取反,最终数组仍然不变;剩余奇数,只需要再排序,对第一个元素取反一次
解答:
class Solution { public int largestSumAfterKNegations(int[] nums, int k) { Arrays.sort(nums); int i = 0; while(k > 0 && i < nums.length && nums[i] < 0) { nums[i] = -nums[i]; k --; i ++; } if(k%2 != 0) { Arrays.sort(nums); nums[0] = -nums[0]; } return Arrays.stream(nums).sum(); } }
我的思路:
没想到如何用贪心思想
对着题解理解,只要gas比cost大,就能找到起始位置;而这个起始位置,只要索引 i 位置上gas < cost,就不断后移更新
解答:
class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int total = 0; int cur = 0; int startIndex = 0; for(int i = 0; i < gas.length; i++) { int diff = gas[i] - cost[i]; total += diff; cur += diff; if(cur < 0) { cur = 0; startIndex = i + 1; } } if(total < 0) { return -1; } return startIndex; } }
我的思路:
理解了题解
首先初始化candy为1,先从前往后遍历,如果rating后一个值大于前一个值,candy数 + 1;接着从后往前遍历,如果rating大于后一个值,比较自身candy数和后一个candy + 1,取较大值
解答:
class Solution { public int candy(int[] ratings) { int n = ratings.length; int[] candy = new int[n]; Arrays.fill(candy, 1); for(int i = 1; i < n; i ++) { if(ratings[i] > ratings[i-1]) { candy[i] = candy[i-1] + 1; } } for(int i = n-2; i >= 0; i--) { if(ratings[i] > ratings[i+1]) { candy[i] = Math.max(candy[i], candy[i+1] + 1); } } int sum = Arrays.stream(candy).sum(); return sum; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。