本题简单一些,估计大家不用想着贪心?,用自己直觉也会有思路。
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 result
本题有点难度,不太好想
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小于0
start = i + 1 # 起始位置更新为i+1
curSum = 0 # curSum重新从0开始累计
if totalSum < 0:
return -1 # 总剩余油量totalSum小于0,说明无法环绕一圈
return start
本题涉及到一个思想,就是想处理好一边再处理另一边,不要两边想着一起兼顾,后面还会有题目用到这个思路?
情况一:右孩子得分比左孩子高 ,其遍历顺序从前往后
情况二:左孩子得分比右孩子高 ,其遍历顺序从后往前
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
?