1、leetcode1005 K次去饭后最大化的数组和
-
思路
- 局部最优:让绝对值大的负数变为正数,当前数值达到最大,整体最优:整个数组和达到最大。
-
代码
-
class Solution { //共使用两次排序 public int largestSumAfterKNegations(int[] nums, int k) { Arrays.sort(nums);//第一次排序 for(int i=0; i<nums.length; i++) { if(nums[i]<0 && k>0) { nums[i] *= -1; k--; } } Arrays.sort(nums);//第二次排序 if( k % 2 == 1) { nums[0] *= -1; } int sum = 0; for(int num : nums) { sum += num; } return sum; } }
-
将数组按照绝对值大小从大到小排序,注意要按照绝对值的大小【可减少一次排序】
class Solution { public int largestSumAfterKNegations(int[] nums, int K) { // 将数组按照绝对值大小从大到小排序,注意要按照绝对值的大小 nums = IntStream.of(nums) .boxed() .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1)) .mapToInt(Integer::intValue).toArray(); int len = nums.length; for (int i = 0; i < len; i++) { //从前向后遍历,遇到负数将其变为正数,同时K-- if (nums[i] < 0 && K > 0) { nums[i] = -nums[i]; K--; } } // 如果K还大于0,那么反复转变数值最小的元素,将K用完 if (K % 2 == 1) nums[len - 1] = -nums[len - 1]; return Arrays.stream(nums).sum(); } }
-
2、leetcode134 加油站
-
思路
- 如果总油量减去总消耗大于等于零那么一定可以跑完一圈,说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
- 每个加油站的剩余量rest[i]为gas[i] - cost[i]。
- i从0开始累加rest[i],和记为curSum,一旦curSum小于零,说明[0, i]区间都不能作为起始位置,因为这个区间选择任何一个位置作为起点,到i这里都会断油,那么起始位置从i+1算起,再从0计算curSum。
-
代码
class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int curSum = 0; int totalSum = 0; int startIndex = 0; for(int i=0; i<gas.length; i++) { curSum += gas[i] - cost[i]; totalSum += gas[i] - cost[i]; if(curSum < 0) { startIndex = (i+1) % gas.length; curSum = 0; } } if(totalSum < 0) { return -1; } return startIndex; } }
3、leetcode135 分发糖果
-
思路
- 先确定右边评分大于左边的情况(也就是从前向后遍历)
- 此时局部最优:只要右边评分比左边大,右边的孩子就多一个糖果,全局最优:相邻的孩子中,评分高的右孩子获得比左边孩子更多的糖果
- 再确定左孩子大于右孩子的情况(从后向前遍历)
- 局部最优:取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量,保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优:相邻的孩子中,评分高的孩子获得更多的糖果。
- 先确定右边评分大于左边的情况(也就是从前向后遍历)
-
代码
class Solution { public int candy(int[] ratings) { int[] candys = new int[ratings.length]; candys[0] = 1; //从前向后 for(int i=1; i<candys.length; i++) { candys[i] = (ratings[i] > ratings[i - 1]) ? candys[i - 1] + 1 : 1; } //从后向前 for(int i=candys.length-2; i>=0; i--) { if(ratings[i] > ratings[i+1]) { candys[i] = Math.max(candys[i], candys[i+1] + 1); } } int candyNums = 0; for(int i=0; i<candys.length; i++) { candyNums += candys[i]; } return candyNums; } }