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

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

题目

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

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

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

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

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

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort()
        count = k
        for i in range(len(nums)):
            if count == 0:
                break
            if nums[i] < 0:
                nums[i] = -nums[i]
                count -= 1
        nums.sort()
        while count > 0:
            nums[0] = -nums[0]
            count -= 1
        return sum(nums)

题目

134.加油站

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

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

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

# 贪心不会超时
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        cur_sum, total_sum, start_position = 0, 0, 0
        for i in range(len(gas)):
            cur_sum += gas[i] - cost[i]
            total_sum += gas[i] - cost[i]
            if cur_sum < 0:
                cur_sum, start_position = 0, i + 1
        if total_sum < 0:
            return -1
        return start_position
# 暴力会超时
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        for i in range(len(gas)):
            start_position, cur_sum = (i +1) % len(gas), gas[i] - cost[i]
            while cur_sum > 0 and start_position != i:
                cur_sum += gas[start_position] - cost[start_position]
                start_position = (start_position + 1) % len(gas)
            if cur_sum >= 0 and start_position == i:
                return i
        return -1

题目

135.分发糖果

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

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

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

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

class Solution:
    def candy(self, ratings: List[int]) -> int:
        left_list = [1] * len(ratings)
        right_list = [1] * len(ratings)
        for i in range(len(ratings) - 1):
            if ratings[i] < ratings[i + 1]:
                left_list[i + 1] = left_list[i] + 1
        for i in range(len(ratings) - 1, 0, -1):
            if ratings[i - 1] > ratings[i]:
                right_list[i - 1] = right_list[i] + 1
        for i in range(len(ratings)):
            left_list[i] = max(left_list[i], right_list[i])
        return sum(left_list)
      
# 代码优化，减少一次循环
class Solution:
    def candy(self, ratings: List[int]) -> int:
        left_list = [1] * len(ratings)
        for i in range(len(ratings) - 1):
            if ratings[i] < ratings[i + 1]:
                left_list[i + 1] = left_list[i] + 1
        for i in range(len(ratings) - 1, 0, -1):
            if ratings[i - 1] > ratings[i]:
                left_list[i - 1] = max(left_list[i] + 1, left_list[i - 1])
        return sum(left_list)