代码随想录学习Day 29

1005.K次取反后最大化的数组和

题目链接

讲解链接

思路：先对数组进行排序，保证数组中最小的值（也就是取反后损失最小的值）位于数组最前端。然后对数组进行遍历，在k次内尽可能将负数全部取反。当数组中元素全部>=0或者k为0时结束循环。此时再对数组进行排序，保证小数在前（因为可能对负数取反后导致原本顺序改变）。然后判断当前的k值，如果为偶数，则直接返回数组和（因为偶数次取反没有影响）；如果是奇数，就将数组中最小的数取反，保证影响最低。

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort()  # 先排序，保证负数在前
        for i in range(len(nums)):
            if nums[i] < 0 and k != 0:  # 尽可能多的将负数取反
                nums[i] = 0 - nums[i]
                k -= 1
            if all(item >= 0 for item in nums) or k == 0:  # 数组中全部>=0或者k为0时结束循环
                break
        nums.sort()  # 再次排序
        if k % 2 == 0:  # k为偶数直接返回sum
            return sum(nums)
        else:
            nums[0] = 0 - nums[0]  # 奇数则对最小的数取反
            return sum(nums)

优化版本，根据绝对值进行排序，可以少进行一次数组排序的操作。

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.加油站

题目链接

讲解链接

暴力解法：

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        for i in range(n):  # 外层i确定起始位置
            cur_gas = gas[i] - cost[i]  # 当前油箱中的油量
            index = (i + 1) % n
            while cur_gas > 0 and index != i:  # 用while循环模拟从i出发行驶一圈的过程
                cur_gas += gas[index] - cost[index]  # 当前油量变化
                index = (index + 1) % n  # 移动到下一个地点，因为是环形所以要取模
            if cur_gas >= 0 and index == i:  # 如果油量还有剩余或者刚好够，并且能够回到出发点
                return i  # 返回出发点的下标
        return -1

贪心法：可以换一个思路，首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。每个加油站的剩余量rest[i]为gas[i] - cost[i]。i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。

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

局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。

全局最优：找到可以跑一圈的起始位置。 

135.分发糖果

题目链接

讲解链接

思路：先从前往后遍历，处理所有右孩子评分大于左孩子评分的情况；在从后往前遍历，处理左孩子评分大于右孩子评分的情况。

局部最优：右边评分比左边大，右边多一个；左边评分比右边大，左边多一个。

全局最优：相邻孩子中，评分高的右孩子糖果比左边孩子多；评分高的左孩子糖果比右边孩子多。

当从后往前遍历时，如果遇到左孩子大于右孩子的情况，还需要考虑之前遍历过程中candy[i]的值，不能直接赋值为candy[i + 1] + 1，而是要取candy[i + 1] + 1 和 candy[i] 最大的糖果数量，candy[i]只有取最大的才能既保持对左边candy[i - 1]的糖果多，也比右边candy[i + 1]的糖果多。

class Solution:
    def candy(self, ratings: List[int]) -> int:
        candy = [1] * len(ratings)  # 初始化candy数组全1，因为每个孩子都至少获得一个糖果
        for i in range(1, len(ratings)):  # 从前往后遍历，考虑右孩子大于左孩子的情况
            if ratings[i] > ratings[i - 1]:  # 如果右大于左
                candy[i] = candy[i - 1] + 1  # 右的糖果数为左+1
        for i in range(len(ratings) - 2, -1, -1):  # 从后往前遍历，考虑左孩子大于右孩子的情况
            if ratings[i] > ratings[i + 1]:  # 如果左大于右
                candy[i] = max(candy[i + 1] + 1, candy[i])  # 取两者最大值
        return sum(candy)  # 返回糖果总和