代码随想录算法训练营第三十三天 | LeetCode 1005. K 次取反后最大化的数组和、134. 加油站、135. 分发糖果

1. LeetCode 1005. K 次取反后最大化的数组和

1.1 思路

1. 本题有两次贪心的选择，第一次贪心在优先对负数取反，再优先对绝对值大的负数取反。第二次贪心是此时若数组里都是非负数时就对最小的非负数进行取反
2. 全局最优：得到数组的最大数组和。找不出明显反例反驳
3. 首先对数组排序，我们要自己实现按照绝对值从大到小排序。然后遍历数组，for(int i=0; i<nums.length; i++)if(nums[i]<0&&k>0)优先对绝对值大的负数取反，nums[i]=-nums[i]，k--。这里就是完成了第一次贪心的策略
4. 此时数组都是非负数了，可能 k 还没用完，接下来就优先对最小的非负数取反。if(k%2==1)nums[nums.length-1]=-nums[nums.length-1]。注意这里数组还是按照绝对值从大到小排序的。这里 k 是奇数就取反，如果是偶数无所谓，因为偶数次取反，非负数还是非负数
5. 以上这么写性能很好

1.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. LeetCode 134. 加油站

2.1 思路

1. 
   
2. 本题虽然是一维数组但是是首尾相连的
3. 这题有补充有消耗，应该关注的是有补充有消耗之后油箱还剩多少油，最终对油箱的油量是增加还是消耗的作用。通过 gas[i]-cost[i] 得到净剩油的数组，这里定义个 curSum 统计我们每一个站点剩余的油量，一旦为负数了就选择下一个站点(i+1)开始。贪心思路：不断累加剩余的油量，一旦在某个站点 curSum 为负数了，说明这个站点(i)之前每个站点作为其实位置都是不行的，因此选择下一个站点(i+1)为起始位置，继续向后遍历。这里有疑问，为什么这个 i 之前的所有位置作为起始位置都是不行的。假设区间 2 的和 curSum>0，从这里开始，区间 1 的和加上区间 2 的和就是 curSum 此时<0，如果区间 2 的和>0，那么区间 1 的和就是<0，那么按照上面的规则就应该是从区间 2 作为起点往后继续累加了
4. 
   
5. 局部最优：当前累加剩余数组 rest[i] 的和 curSum 一旦小于 0，起始位置至少要是 i+1，因为从 i 之前开始一定不行。
6. 全局最优：找到可以跑一圈的起始位置。
7. 定义个 curSum 统计从头开始每一站的剩余油量，totalSum 把所有剩余油量加起来如果<0，说明从任何一个位置跑的话都不可能跑完一圈，定义个 start，如果 curSum<0 就从 i+1 开始
8. for(int i=0; i<gas.length; i++)curSum+=(gas[i]-cost[i])，totalSum+=(gas[i]-cost[i])，if(curSum<0)start=i+1，并且 curSum=0 重新开始统计。
9. 退出循环后 if(totalSum<0)return -1；最后 return start 即可
10. 按照这个思路到最后一个位置的时候已经可以确定没有结果了

2.2 代码

//
// 解法2
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) % gas.length ; 
                curSum = 0;
            }
        }
        if (totalSum < 0) return -1;
        return index;
    }
}

3. LeetCode 135. 分发糖果

3.1 思路

1. 每个小孩至少 1 个糖果，得分高的小孩比旁边低分的糖果要多糖果，但最终是求最少的给糖果数量
2. 我们的难题是要和两边的小孩一起进行比较。不少题都有这种情况，两边一起比较就很容易乱，这种题解题思路一定是先确定一边再确定另一边。
3. 首先先看情况 1：右边比左边得分高，if(rating[i-1]<rating[i]) 这个 candy[i]=candy[i-1]+1。这就是右边比左边得分高的处理方式。注意这里是从左向右遍历
4. 情况 2：左边比右边高，注意这里是从右向左遍历，为什么？因为这种情况如果从左向右遍历是无法使用到情况 1 处理的结果的，因为比较依赖第 i+1 个元素。 if(rating[i]>rating[i+1]) 这个 candy[i]=canddy[i+1]+1，由于情况 1 也算了个 candy[i] 我们要在两者间取个值，我们此时如果这个孩子得分比较高是要既比左边大又要比右边大的，因此要比较求最大值，所以实际上 candy[i]=Math.max(candy[i+1]+1，candy[i])，算完以后 candy[i] 就是每个小孩子应得的糖果数，最后累加就是我们要求的结果
5. 定义数组 candy，candy[0]=1；情况 1 for(int i=1;i<rating.length; i++) 从 1 开始是因为最开始是从 i 和 i-1 比较，if(rating[i-1]<rating[i-1])candy[i]=candy[i-1]+1，否则就是 candy[i]=1；
6. 情况 2 for(int i=rating.length-2; i>=0; i--)，从这个位置开始是因为 rating.length-1 是最后一个位置，而最开始是最后一个位置和倒数第二个位置比较，即 i(倒数第二) 和 i+1(最后一个)，if(rating[i]>rating[i+1]) candy[i]=Math.max(candy[i+1]+1，candy[i])
7. 最后定义个 result 累加 candy 数组，然后返回 result 即可

3.2 代码

//
class Solution {
    /**
         分两个阶段
         1、起点下标1 从左往右，只要 右边 比 左边 大，右边的糖果=左边 + 1
         2、起点下标 ratings.length - 2 从右往左， 只要左边 比 右边 大，此时 左边的糖果应该 取本身的糖果数（符合比它左边大） 和 右边糖果数 + 1 二者的最大值，这样才符合 它比它左边的大，也比它右边大
    */
    public int candy(int[] ratings) {
        int len = ratings.length;
        int[] candyVec = new int[len];
        candyVec[0] = 1;
        for (int i = 1; i < len; i++) {
            candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;
        }
        for (int i = len - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
            }
        }
        int ans = 0;
        for (int num : candyVec) {
            ans += num;
        }
        return ans;
    }
}