算法训练营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
}