算法训练营Day34(贪心3)

发布时间:2024年01月19日

1005.K次取反后最大化的数组和?. - 力扣(LeetCode)?

提醒

本题简单一些,估计大家不用想着贪心?,用自己直觉也会有思路。

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        A.sort(key=lambda x: abs(x), reverse=True)  # 第一步:按照绝对值降序排序数组A
        for i in range(len(A)):  # 第二步:执行K次取反操作
            if A[i] < 0 and K > 0:
                A[i] *= -1
                K -= 1
        if K % 2 == 1:  # 第三步:如果K还有剩余次数,将绝对值最小的元素取反
            A[-1] *= -1
        result = sum(A)  # 第四步:计算数组A的元素和
        return result

?134.?加油站?力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

提醒

本题有点难度,不太好想

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        curSum = 0  # 当前累计的剩余油量
        totalSum = 0  # 总剩余油量
        start = 0  # 起始位置
        
        for i in range(len(gas)):
            curSum += gas[i] - cost[i]
            totalSum += gas[i] - cost[i]
            if curSum < 0:  # 当前累计剩余油量curSum小于0
                start = i + 1  # 起始位置更新为i+1
                curSum = 0  # curSum重新从0开始累计
        if totalSum < 0:
            return -1  # 总剩余油量totalSum小于0,说明无法环绕一圈
        return start

?135.?分发糖果?力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

提醒

本题涉及到一个思想,就是想处理好一边再处理另一边,不要两边想着一起兼顾,后面还会有题目用到这个思路?

情况一:右孩子得分比左孩子高 ,其遍历顺序从前往后

情况二:左孩子得分比右孩子高 ,其遍历顺序从后往前

class Solution:
    def candy(self, ratings: List[int]) -> int:
        candyVec = [1] * len(ratings)
        # 从前向后遍历,处理右侧比左侧评分高的情况
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                candyVec[i] = candyVec[i - 1] + 1
        
        # 从后向前遍历,处理左侧比右侧评分高的情况
        for i in range(len(ratings) - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1)
        
        # 统计结果
        result = sum(candyVec)
        return result

?

文章来源:https://blog.csdn.net/2301_79788081/article/details/135653628
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。