class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
nums.sort(key=lambda x:abs(x), reverse=True)
for i in range(len(nums)):
if nums[i] < 0 and k > 0:
nums[i] *= -1
k -= 1
if k % 2 == 1:
nums[-1] *= -1
return sum(nums)
134. 加油站
1、暴力法
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
for i in range(len(gas)):
rest = gas[i] - cost[i] # 剩余汽油量
index = (i + 1) % len(gas) # 到达第几个加油站
# 从第 i 个汽油站出发
while rest > 0 and index != i:
rest += gas[index] - cost[index]
index = (index + 1) % len(gas)
# 跑完一圈且汽油量大于等于0:
if rest >= 0 and index == i:
return i
return -1
2、贪心法
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
cur_gas = 0
total_gas = 0
start = 0
for i in range(len(gas)):
cur_gas += gas[i] - cost[i]
total_gas += gas[i] - cost[i]
if cur_gas < 0:
start = i + 1
cur_gas = 0
if total_gas < 0:
return -1
return start
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
res = [1] * n
# 从左到右遍历
for i in range(1, n):
if ratings[i] > ratings[i-1]:
res[i] = res[i-1] + 1
# 从右到左遍历
for j in range(n-2, -1, -1):
if ratings[j] > ratings[j+1]:
res[j] = max(res[j], res[j+1] + 1)
return sum(res)