本文主要是介绍代码随想录算法训练营第三十三天丨1005. K 次取反后最大化的数组和、134. 加油站、135. 分发糖果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1005. K 次取反后最大化的数组和
两次贪心：
先按绝对值排序，第一次从大到小反转绝对值大的负值。如果数组都非负了k还有剩余，一直反转绝对值最小的值直到k为0。
class Solution:def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:nums.sort(key = abs, reverse = True)for i in range(len(nums)):if k == 0:breakelif nums[i] < 0:nums[i] *= -1k -= 1print(nums)if k > 0:nums[-1] = (-1) ** k * nums[-1]return sum(nums) 134. 加油站
我的思路：
我的想法是，计算两个数组的差值数组，元素表示的就是从i 到 i + 1剩余的油量。由于是环形路线，将diff数组扩展一倍，如果存在非负最大子数组，最大子数组的起始点就是结果。
class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:diffs = [gas[i] - cost[i] for i in range(len(gas))] * 2cur_max = global_max = diffs[0]i = 0for pos in range(1, len(diffs)):if cur_max < 0:i = poscur_max = diffs[pos]else:cur_max += diffs[pos]global_max = max(cur_max, global_max)return i if i < len(gas) else -1优化：
实际上没有想到这道题的精髓，这道题不需要求最大子数组，大小什么的都无所谓，只要能是非负的就可以了。
首先要明确一点，如果总油量大于总消耗，一定从某点开始可以环绕一周，算法就是按照证明这一点设计的。如果总油量小于总消耗不能绕一周很好理解，那如何证明总油量不小于总消耗，一定可以环绕一周呢。
情况一：如果从0开始一直到n - 1一直是非负差值和，根据总油量不少于总消耗，说明从0开始就能绕一周，不需证明。
情况二：从0开始到i，在i处发现差值和为负，这说明从0到i总油量小于总消耗，从0到i任意一点开始无法到达i+1，但是整个环形线路总油量是大于总消耗的，说明假如从i + 1起步，i + 1到 n - 1之间，总油量是严格大于总消耗的，并且差值至少是之前累计的所有的负值。因此，把起始点移动到i + 1，继续累计差值，每次发现差值和为负，继续寻找下一个作为起点，直到某次ik + 1到 n - 1的差值和总为正，这说明从ik + 1不仅能到n - 1，还能弥补之前所有的负值和到达ik，因为总油量不小于总消耗，最终从ik能够到达ik + 1，ik + 1就是起点。
class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:start = curSum = totalSum = 0for i in range(len(gas)):curSum += gas[i] - cost[i]totalSum += gas[i] - cost[i]if curSum < 0:start = i + 1curSum = 0if totalSum < 0: return -1 return start135. 分发糖果
一次从左向右遍历，确保每个孩子比他左边评分高的孩子获得更多的糖果；另一次从右向左遍历，确保每个孩子比他右边评分高的孩子获得更多的糖果。通过这两次遍历，可以保证所有孩子的糖果数既满足左边的条件，也满足右边的条件。
class Solution:def candy(self, ratings: List[int]) -> int:n = len(ratings)candies = [1] * n# 从左向右确保评分高的孩子比他左边的孩子获得更多的糖果for i in range(1, n):if ratings[i] > ratings[i - 1]:candies[i] = candies[i - 1] + 1# 从右向左确保评分高的孩子比他右边的孩子获得更多的糖果for i in range(n - 2, -1, -1):if ratings[i] > ratings[i + 1]:candies[i] = max(candies[i], candies[i + 1] + 1)# 计算总糖果数return sum(candies)好难想到的。
这篇关于代码随想录算法训练营第三十三天丨1005. K 次取反后最大化的数组和、134. 加油站、135. 分发糖果的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
