代码随想录算法训练营|day33

贪心：
先对数组排序，若数组存在负数，且k > 0，遍历数组将其变为正数；若将数组整个变为正数，k依旧未用完，重新排序；若k为奇数，将nums[0]变为相反数，求和，否则直接求和

func largestSumAfterKNegations(nums []int, k int) int {sort.Ints(nums)for i := 0; i < len(nums); i++ {if nums[i] < 0 && k > 0 {nums[i] = -nums[i]k--}}sort.Ints(nums)if k%2 == 1 {nums[0] = -nums[0]}res := 0for _, num := range nums {res += num}return res
}

贪心：
如果sum(gas) > sum(cost)，证明不可能跑完全程；
若能跑完全程，若当前累计gas-cost之和小于0，证明不可能为起点，选取下一点为起点。直到遍历结束

func canCompleteCircuit(gas []int, cost []int) int {sum := 0for i := 0; i < len(gas); i++ {sum += gas[i] - cost[i]}if sum < 0 {return -1}res, index := 0, 0for i := 0; i < len(gas); i++ {res += gas[i] - cost[i]if res < 0 {index, res = i+1, 0}}return index
}

贪心：
保证每人有一个糖果；从左向右遍历，若右边比左边大，糖果值+1； 通途
从右向左遍历，若左边比右边大，糖果值取max(当前值,右边孩子糖果值+1）
第一个变化位置处取值大

func candy(ratings []int) int {candy := make([]int, len(ratings))for i := 0; i < len(candy); i++ {candy[i] = 1}for i := 1; i < len(ratings); i++ {if ratings[i] > ratings[i-1] {candy[i] = candy[i-1] + 1}}for i := len(ratings) - 2; i >= 0; i-- {if ratings[i] > ratings[i+1] {candy[i] = max(candy[i], candy[i+1]+1)}}sum := 0for i := 0; i < len(ratings); i++ {sum += candy[i]}return sum
}