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

本文主要是介绍代码随想录算法训练营第三十六天 | 1005.K次取反后最大化的数组和、134.加油站、135.分发糖果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

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

思路

代码

代码

134.加油站

思路

代码

135.分发糖果

思路

代码

---

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

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

代码随想录

思路

        直觉，直接写，没什么好讲的。

代码

class Solution:def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:for i in range(k):num = min(nums)num_index = nums.index(num)nums[num_index] = -numreturn sum(nums)

但是 ，Carl居然不是这么写的，（好吧python是在作弊），他是这么写的：

• 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
• 第二步：从前向后遍历，遇到负数将其变为正数，同时K--
• 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
• 第四步：求和

代码

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

---

134.加油站

本题有点难度，不太好想，推荐大家熟悉一下方法二

代码随想录

思路

        我想的方法原来是暴力法。。。计算每次rest = gas[i] - cost[i]的值，如果是正数，就继续指针向右， rest累加上去，如果出现rest是负数，那就说明原来的点不能作为起点，尝试下一个点。（这样分分钟超时了，每日崩溃1/1）

        而Carl哥却推出了一个结论：i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。

在i这里失败，下一次直接从i+1开始 ！！！这样就节省了很多时间了。你可以自己看链接里的证明，看不懂可以给我评论，我画给你看。

代码

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小于0start = i + 1  # 起始位置更新为i+1curSum = 0  # curSum重新从0开始累计if totalSum < 0:return -1  # 总剩余油量totalSum小于0，说明无法环绕一圈return start

---

135.分发糖果

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

代码随想录

思路

        绝，真绝了。既然我没办法一次兼顾两边我就一直只兼顾一边，先从左向右遍历，判断每个数是不是大于左边的那个数，是的话就在左边那个数的基础上+1。然后从右向左遍历，判断每个数是不是大于右边那个数，是的话，如果在右边那个数的基础上加大于原来的数，就更新。

        为什么是从右向左遍历：（自己总结的，Carl说的那个我听得有点迷糊，所以我选择自己消化完讲给你们听，所以给我点个赞或者收藏一下吧QWQ）

 如果从左边遍历起，我们就看最后那个三个孩子，孩子4得分比孩子5得分多，那孩子4就在孩子5的得分基础上+1，然后孩子5得分比孩子6多，在孩子6的基础上+1，这样糖果就是2,2,1。

如果从右边遍历起，孩子5得分比孩子4多，孩子5在孩子4的基础上糖果+1，同理，孩子4糖果在孩子5基础上+1，那就是3,2,1。 

你看，是不是利用了孩子5和孩子6之间的比较。而孩子6的右边是空气，所以就不存在这种问题了。（即和左边的孩子比较要从左到右，和右边孩子的比较要从右到左）

代码

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

这篇关于代码随想录算法训练营第三十六天 | 1005.K次取反后最大化的数组和、134.加油站、135.分发糖果的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---