代码随想录算法训练营Day34 (Day33休息) | 贪心算法(3/6) LeetCode 1005.K次取反后最大化的数组和 134. 加油站 135. 分发糖果

开始第三天的练习。贪心算法没有固定套路，能由局部推出最佳就能用贪心！

第一题

1005. Maximize Sum Of Array After K Negations

Given an integer array nums and an integer k, modify the array in the following way:

• choose an index i and replace nums[i] with -nums[i].

You should apply this process exactly k times. You may choose the same index i multiple times.

Return the largest possible sum of the array after modifying it in this way.

一个数列，更改k次，为了让数列最后的值最大，因此应该优先更改负数中绝对值最大的数，其次更改0，这样能让结果最大，或者对总和没有影响。

当一个数列都是正的时候，又要更改绝对值最小的数，让总和减少的尽可能少。这些都是贪心的思路。

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort(key=lambda x: abs(x), reverse=True)  
 
        for i in range(len(nums)):  
            if nums[i] < 0 and k > 0:
                nums[i] *= -1
                k -= 1
 
        if k % 2 == 1:  
            nums[-1] *= -1
 
        result = sum(nums)  
        return result

第二题

134. Gas Station

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

测试用例已经确认结果是唯一的，因此可以简单确认一下是否有解：就是加的油大于加油站的距离，那这道题可能有解。

在遍历的时候，从头到尾适合用for遍历，而头尾循环适合用while。

还有一个可以简化思路的方法，就是记录从头开始累加的油量，如果有一处的油量达到负值，那这个地方不能作为起点，不然会断油。

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        curSum = 0  
        totalSum = 0  
        start = 0 
        for i in range(len(gas)):
            curSum += gas[i] - cost[i]
            totalSum += gas[i] - cost[i]
            
            if curSum < 0: 
                start = i + 1 
                curSum = 0 
        if totalSum < 0:
            return -1  
        return start

第三题

135. Candy

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

从一边开始遍历，只需要保证相邻的孩子，分数高的分配到比分数低的孩子多一个糖就行，如果相邻分数一样，糖的个数甚至可以更少。

然后再反过来遍历，确保一个孩子的另一边相邻的分数。

两个方向不能同时遍历，不然会顾此失彼

class Solution:
    def candy(self, ratings: List[int]) -> int:
        candyVec = [1] * len(ratings)    
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                candyVec[i] = candyVec[i - 1] + 1
        
        for i in range(len(ratings) - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1)
        
        result = sum(candyVec)
        return result