34天【代码随想录算法训练营34期】第八章 贪心算法 part03 (● 1005.K次取反后最大化的数组和 ● 134. 加油站 ● 135. 分发糖果 )

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

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 != 0:
            nums[-1] *= -1
        return sum(nums)

134. 加油站

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        current_sum = 0
        total_sum = 0
        start = 0

        for i in range(len(gas)):
            current_sum += gas[i] - cost[i]
            total_sum += gas[i] - cost[i]

            if current_sum < 0:
                start = i+1
                current_sum = 0
        
        if total_sum < 0:
            return -1
        return start

135. 分发糖果

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