代码随想录算法训练营第三十四天| LeetCode1005. K 次取反后最大化的数组和、LeetCode134. 加油站、LeetCode135. 分发糖果

一、LeetCode1005. K 次取反后最大化的数组和

        1：题目描述（1005. K 次取反后最大化的数组和）

        给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

• 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

        重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

        以这种方式修改数组后，返回数组 可能的最大和 。

        2：解题思路

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        # 有负数，最小的负数先取相反数，这样得到的和是最大的
        # 有正数，最小的正数先取相反数，这样得到的和也是最大的
        # 对nums按绝对值从大到小进行排序，这样绝对值最小的值就在最后面
        nums = sorted(nums, key=abs, reverse=True)           
        for i in range(len(nums)):
            # 遍历nums，当k>0并且nums[i]小于0，说明此时的负数是最小的
            if k > 0 and nums[i] < 0:
                # 取其相反数
                nums[i] = -nums[i]
                # k减1
                k -= 1
        # 当遍历完nums后，k任然大于0
        # 此时nums中的数为非负数，最小的值在后面
        # 此时只需要将最后面的元素进行剩余k次的取相反数，就可得到最大和
        if k > 0:
            nums[-1] *= (-1)**k            # (-1)**k中的-1需要用括号扩起来
        return sum(nums)

二、LeetCode134. 加油站

        1：题目描述（134. 加油站）

        在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

        你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

        给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

        2：解题思路

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # 暴力法---超时了
        # # 以gas的每个点作为起点，看是否能绕行一周
        # for i in range(len(gas)):
        #     rest = gas[i] - cost[i]         # 记录从i到i+1所剩余的油量
        #     index = (i+1)%len(gas)          # 记录下一个到到达的加油站
        #     while rest > 0 and index != i:
        #         rest += gas[index] - cost[index]     # 叠加剩余的油量
        #         index = (index+1)%len(gas)    # 下一个加油站
        #     # 如果跑完一圈剩余的油量大于等于0，则存在解
        #     if rest >= 0 and index == i:
        #         return i
        # # 遍历完所有的起点，都没有符合要求的，就返回-1
        # return -1
        
        start = 0          # 加油站的起始位置
        curSum = 0         
        totalSum = 0       # 统计剩余的油量
        # 从第0个加油站开始计算剩余油量
        for i in range(len(gas)):
            curSum += gas[i] - cost[i]       # 统计剩余油量
            totalSum += gas[i] - cost[i]     # 统计剩余油量
            if curSum < 0:
                # 当剩余油量小于0，说明已i之前的站点为起点，就已经不够行使到当前加油站了
                curSum = 0                   # 重置剩余油量，为0
                start = i+1                  # 起始位置为下一个加油站
        if totalSum < 0:
            # 剩余的油量小于0，则不能行使一周
            return -1
        # 最后剩余的油量大于等于0，则从start为起点可以绕行一周
        return start

三、LeetCode135. 分发糖果

        1：题目描述（135. 分发糖果）

        n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

        你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

        请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

        2：解题思路

class Solution:
    def candy(self, ratings: List[int]) -> int:
        candyVec = [1] * len(ratings)          # 先定义每个孩子分配到1个糖果
        # 从左向右遍历，若当前孩子的评分高于前一个孩子时，当前孩子就比前一个孩子多分配一个糖果
        for i in range(1,len(ratings)):
            if ratings[i] > ratings[i-1]:
                candyVec[i] = candyVec[i-1] + 1
        # 从右向左遍历，若当前孩子的评分高于后面一个孩子，当前孩子需要比后一个孩子多分配一个糖果
        for j in range(len(ratings)-2, -1, -1):
            if ratings[j] > ratings[j+1]:
                # 因为相邻两个孩子评分更高的孩子获得更多的糖果
                # 所以当前孩子所获得的糖果需要在当前已获得的糖果（之前比较右孩子大于左孩子得到的糖果数量）和比后一个孩子多分配一个糖果中取最大值
                # 只有取最大的才能既保持对左边candyVec[i - 1]的糖果多，也比右边candyVec[i + 1]的糖果多
                candyVec[j] = max(candyVec[j], candyVec[j+1]+1)
        return sum(candyVec)