贪心算法1005|134|135

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

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

134加油站

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

135分发糖果

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