本文主要是介绍【代码随想录训练营】【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)
这篇关于【代码随想录训练营】【Day 36】【贪心-3】| Leetcode 1005, 134, 135的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!