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 result134.加油站
暴力解法：
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) # 返回糖果总和