做类似猪八戒网的网站,wordpress中文版 乱码,电子商务公司是做什么的,电商运营培训课程视频【代码随想录训练营】【Day 36】【贪心-3】| Leetcode 1005, 134, 135
需强化知识点
题目
1005. K 次取反后最大化的数组和
贪心#xff1a;翻转绝对值最小的数思路#xff1a;将数组按绝对值降序排序后#xff0c;从左向右遍历数组#xff0c;如果遇到小于0的数并且还…【代码随想录训练营】【Day 36】【贪心-3】| Leetcode 1005, 134, 135
需强化知识点
题目
1005. K 次取反后最大化的数组和
贪心翻转绝对值最小的数思路将数组按绝对值降序排序后从左向右遍历数组如果遇到小于0的数并且还有取反次数即取反如果最后还剩有取反次数就取反绝对值最小的数
class Solution:def largestSumAfterKNegations(self, nums: List[int], k: int) - int:nums.sort(keylambda x: abs(x), reverseTrue)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 那么起始点更新为 i1 最后判断只要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 startIndex135. 分发糖果
思路两次遍历先从左往右判定 当前孩子与左孩子的情况从右往左判定当前孩子与右孩子的情况如果分数更大则该孩子的糖果数更新为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[i1]:curCandy[i] max(curCandy[i], curCandy[i1] 1)return sum(curCandy)
