【代码随想录训练营】【Day 36】【贪心-3】| Leetcode 1005, 134, 135

【代码随想录训练营】【Day 36】【贪心-3】| Leetcode 1005, 134, 135

需强化知识点

题目

1005. 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] = - nums[i]k -= 1if k > 0 and k % 2 == 1:nums[-1] = - nums[-1]return sum(nums)

134. 加油站

• 思路：记录从每个加油站出发后的剩余汽油数 gas[i] - cost[i]， 并累加得到 totalSum， curSum，如果curSum 小于 0 ，那么起始点更新为 i+1， 最后判断，只要totalSum 小于0，则返回-1
• 注意 startIndex 的初始值为0

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

135. 分发糖果

• 思路：两次遍历，先从左往右，判定 当前孩子与左孩子的情况，从右往左，判定当前孩子与右孩子的情况，如果分数更大，则该孩子的糖果数更新为max(curCandy[i], curCandy[i-1] + 1)
• 注意：糖果更新，不能使用result 直接 加 1，因为会存在目前糖果数已经满足条件的情况

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