贪心算法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)