今日任务：
资料来源：
题目
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。
示例 1：
输入：nums = [4,2,3], k = 1 输出：5 解释：选择下标 1 ，nums 变为 [4,-2,3] 。
示例 2：
输入：nums = [3,-1,0,2], k = 3 输出：6 解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
示例 3：
输入：nums = [2,-3,-1,5,-4], k = 2 输出：13 解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
提示：
一个贪心是，尽量选择绝对值大的负数进行变换，另一个贪心是，如果没得负数可换了，就选择绝对值尽量小的数字反复变换。
pythonfrom typing import List
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
nums.sort(key=lambda x: abs(x), reverse=True) # 绝对值排序
index = 0
while index < len(nums) - 1 and k > 0:
if nums[index] < 0:
nums[index] = -nums[index]
k -= 1
index += 1
if k > 0:
for i in range(k):
nums[-1] = - nums[-1]
return sum(nums)
题目
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
示例 1:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2] 输出: 3 解释: 从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油 开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油 开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油 开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油 开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油 开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。 因此，3 可为起始索引。
示例 2:
输入: gas = [2,3,4], cost = [3,4,3] 输出: -1 解释: 你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。 我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油 开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油 开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油 你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。 因此，无论怎样，你都不可能绕环路行驶一周。
提示:
第一次做的时候想的是思路一，该思路整体如下：假设我从第一个加油站出发准备转一圈，一旦我的油箱出现负数，就说明我出发的这个起点不能用，需要一直向后寻找新的出发点，直到某一个加油站时我目前的油箱是正数了，再继续出发。如此往复直到出发的点和当前所在的加油站重合。此时如果我的油箱>=0，那么说明此时的出发点是可以走完全程的；如果此时我的油箱是负数，那么说明无论怎么跑都无法完成一圈。
python# 我的代码
from typing import List
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
oil_balance = [0] * len(gas) # 这个可以优化掉的
for i in range(len(gas)):
oil_balance[i] = gas[i] - cost[i]
# 正数意味着可以到达 有多余的油 负数意味着不可以到达
start_index = 0
end_index = 0
balance = oil_balance[end_index] # 当前油箱
while (end_index - start_index) != len(gas) - 1:
if balance < 0: # 向前起点
start_index -= 1
balance += oil_balance[start_index]
else: # 向后继续走
end_index += 1
balance += oil_balance[end_index]
if balance >= 0:
if start_index == 0:
return 0
else:
return len(gas) + start_index
else:
return -1
第二种解法说实话，感觉和第一种解法有点相似。第一种解法相当于是向前找起点，第二种解法就是向后找起点。同样是对数组进行循环，同样是计算油箱，不同的是解法二在油箱为负数时认为从第一个加油站到当前加油站都不可能是起点，从当前加油站的下一个加油站为起点开始重新计算油箱。同时，解法二还在循环中计算总的路程和油的多少。循环结束时，如果油数量小于路程，就说明无论从哪里开始都不能走完一圈，返回-1；如果油数量大于路程，就返回当前计算的油箱所对应的那个起点。
题目
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。 相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
示例 1：
输入：ratings = [1,0,2] 输出：5 解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2：
输入：ratings = [1,2,2] 输出：4 解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
提示：
这题体现了贪心的特点：不好想，但是一旦想出来就相当好做。整体的思路就是从前向后和从后向前两次遍历，分别检查当前孩子比左边孩子大和当前孩子比右边孩子大两种情况。它之所以成立，是因为第一次检查时，不仅保留了糖果数量，也保留了当前孩子和左边孩子的大小关系。等到第二遍遍历检查当前孩子和右边孩子的大小关系时，由于是取max，所以再怎么修改当前孩子的糖果数也不会小于之前的糖果数，当前孩子和左边孩子的大小关系也就得到了保留。
pythonfrom typing import List
class Solution:
def candy(self, ratings: List[int]) -> int:
candy_list = [1] * len(ratings)
for i in range(1, len(ratings)): # 从前向后 检查当前孩子比左边孩子大的情况
if ratings[i] > ratings[i - 1]:
candy_list[i] = candy_list[i - 1] + 1
for i in range(len(ratings) - 2, -1, -1): # 从后向前 检查当前孩子比右边孩子大的情况
if ratings[i] > ratings[i + 1]:
candy_list[i] = max(candy_list[i], candy_list[i + 1] + 1)
return sum(candy_list)
本文作者:御坂19327号
本文链接:
版权声明:本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！