代码随想录day32【贪心算法】K次取反后最大化的数组 加油站 分发糖果

K次取反后最大化的数组

力扣题目链接
局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。
如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让数组和 达到最大。

那么又是一个贪心：局部最优：只找数值最小的正整数进行反转，当前数值和可以达到最大（例如正整数数组{5, 3, 1}，反转1 得到-1 比 反转5得到的-5 大多了），全局最优：整个 数组和 达到最大。

//自己写的，时间复杂度和空间复杂度高。

var largestSumAfterKNegations = function(nums, k) {
   while (k--) {
    nums.sort((a, b) => {
      return a - b;
    });
    nums[0] = -nums[0];
  }

  return nums.reduce((pre, cur) => {
    return pre + cur;
  }, 0);
  
};

改进：
通过采用绝对值排序，先把负数转换，未用完的k，再从正数中，找最后一个值，不必每次转换，通过奇偶数判断最后的正负。

var largestSumAfterKNegations = function(nums, k) {
   nums.sort((a,b)=>{
       return Math.abs(b)-Math.abs(a)
   })
   for(let i in nums){
       if(nums[i]<0 && k>0){
           nums[i]=-nums[i]
           k--
       }
   }
   if( k % 2 === 1){
       nums[nums.length-1]=-nums[nums.length-1]
   }
   return nums.reduce((pre,cur)=>{
       return pre+cur
   },0)
};

加油站

思路：
局部最优：当前累加和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。
全局最优：找到可以跑一圈的起始位置。

image.png

力扣题目链接

var canCompleteCircuit = function(gas, cost) {
    let curSum=0
    let totalSum=0
    let res =0

    for(let i=0;i<gas.length;i++){
        curSum += gas[i]-cost[i]
        totalSum +=gas[i]-cost[i]
        if(curSum<0){
            res = i+1
            curSum=0
        }
    }
    if(totalSum<0) return -1
    return res
};

分发糖果

力扣题目链接

思路：
确定一边之后，再确定另一边，

1. 右边比左边大：
   局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
2. 左边比右边大：
   局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。

var candy = function(ratings) {
    let candy =[]
    candy[0]=1
    for(let i=1;i<ratings.length;i++){
        if(ratings[i]>ratings[i-1]){
            candy[i]=candy[i-1]+1
        }else{
            candy[i]=1
        }
    }

    for(let i=ratings.length-2;i>=0;i--){
        if(ratings[i]>ratings[i+1]){
            candy[i]=Math.max(candy[i+1]+1,candy[i])
        }
    }
    return candy.reduce((pre,cur)=>{
        return pre+cur
    },0)
};