算法训练营day29, 贪心算法3

import (

  "sort"

)

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

func largestSumAfterKNegations(nums []int, k int) int {

  //先从小到大排序

  sort.Ints(nums)

  sum := 0

  //将数组中负数转为正数

  for i := 0; i < len(nums); i++ {

    if nums[i] < 0 && k > 0 {

      nums[i] = -nums[i]

      k--

    }

  }

  //二次排序

  sort.Ints(nums)

  //如果k还没用完且为奇数，把最小值转为负数，影响最小

  if k > 0 && k%2 == 1 {

    nums[0] = -nums[0]

  }

  for i := 0; i < len(nums); i++ {

    sum += nums[i]

  }

  return sum

}

//134. 加油站

func canCompleteCircuit(gas []int, cost []int) int {

  curSum := 0 //统计油箱剩余量

  sum := 0   //统计所有加油站油耗剩余

  index := 0 //出发时加油站的编号

  for i := 0; i < len(gas); i++ {

    curSum += (gas[i] - cost[i])

    sum += (gas[i] - cost[i])

    //如油箱剩余量小于零则把下标移动到下一个，同时油箱归零

    if curSum < 0 {

      index = i + 1

      curSum = 0

    }

  }

  //如果所有加油站油耗剩余小于零则说明无法跑完一圈返回-1

  if sum < 0 {

    return -1

  }

  return index

}

//135. 分发糖果

func candy(ratings []int) int {

  n := len(ratings)

  candys := make([]int, n)

  candySum := 0

  //先想左统计一圈

  candys[0] = 1

  for i := 0; i < n-1; i++ {

    if ratings[i+1] > ratings[i] {

      candys[i+1] = candys[i] + 1

    } else {

      candys[i+1] = 1

    }

  }

  //在向右统计一圈

  for i := n - 1; i > 0; i-- {

    if ratings[i-1] > ratings[i] {

      //比较当前值和前一个值+1中取二者最大值

      if candys[i-1] < candys[i]+1 {

        candys[i-1] = candys[i] + 1

      }

    }

  }

  for i := 0; i < n; i++ {

    candySum += candys[i]

  }

  return candySum

}