day33

1、leetcode1005 K次去饭后最大化的数组和

1. 思路

   • 局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。

2. 代码

   1. 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;
          }
      }
      

   2. 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小【可减少一次排序】

      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 加油站

1. 思路

   • 如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
   • 每个加油站的剩余量rest[i]为gas[i] - cost[i]。
   • i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。

2. 代码

   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 分发糖果

1. 思路

   1. 先确定右边评分大于左边的情况（也就是从前向后遍历）
      • 此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
   2. 再确定左孩子大于右孩子的情况（从后向前遍历）
      • 局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。

2. 代码

   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;
       }
   }