赞
踩
1005.K次取反后最大化的数组和
134.加油站
135.分发糖果
语言:Java
链接:https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
class Solution { public int largestSumAfterKNegations(int[] nums, int k) { Arrays.sort(nums); int sum = 0; int idx = 0; //用于记录要进行取负操作的下标 //取负顺序 //先对所有负数取负 //如果处理完所有负数后k还不为0,就对绝对值最小的整数不断取负 for(int i = 0; i < k; i++){ if(i < nums.length - 1 && nums[idx] < 0){ //如果排序后的数组开头有一堆负数,idx会一直加加 nums[idx] = -nums[idx]; //绝对值最小的元素只能在最大负数/最小正数处取得 //idx最后会落到绝对值最小数处 //不要忘记等于号,否则相邻两数为绝对值相同的负数时,idx不会前进 if(Math.abs(nums[idx]) >= Math.abs(nums[idx + 1])){ idx++; } continue; } nums[idx] = -nums[idx]; } for(int i = 0; i < nums.length; i++){ sum += nums[i]; } return sum; } }
链接:https://leetcode.cn/problems/gas-station/
class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int curSum = 0; int totalSum = 0; int ret = 0; for(int i = 0; i < gas.length; i++){ curSum += gas[i] - cost[i]; totalSum += gas[i] - cost[i]; if(curSum < 0){ ret = i + 1; curSum = 0; } } if(totalSum < 0){ return -1; } return ret; } }
链接:https://leetcode.cn/problems/candy/
两侧分别求最优-局部最优
最终得到整体最优
class Solution { public int candy(int[] ratings) { int[] arr = new int[ratings.length]; for(int i = 0; i < ratings.length; i++){ arr[i] = 1; } int sum = 0; for(int i = 1; i < ratings.length; i++){ if(ratings[i] > ratings[i - 1]){ //右比左大 arr[i] = arr[i - 1] + 1; } } for(int i = ratings.length - 2; i >= 0; i--){ if(ratings[i] > ratings[i + 1]){ //左比右大 arr[i] = Math.max(arr[i + 1] + 1, arr[i]); } } for(int i = 0; i < ratings.length; i++){ sum += arr[i]; } return sum; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。