大家好，又见面了，我是你们的朋友全栈君。
0. 差分数组的概念：
常用于某个区间值都需加/减去a的问题。
1. 1094拼车
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
max_val = 0
for i in range(len(trips)):
max_val = max(max_val, trips[i][2])
diff = [0]*(max_val+2)
for i in range(len(trips)):
diff[trips[i][1]] += trips[i][0]
diff[trips[i][2]] -= trips[i][0]
sum_val = 0
flag = True
for i in range(len(diff)):
sum_val +=diff[i]
if sum_val > capacity:
flag = False
break
return flag
2. 1109航班预定统计
class Solution:
def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
diff = [0]*(n+2)
res = [0]*n
sum_val = 0
for i in range(len(bookings)):
diff[bookings[i][0]] += bookings[i][2]
diff[bookings[i][1]+1] -= bookings[i][2]
for i in range(1,n+1):
sum_val+= diff[i]
res[i-1] = sum_val
return res
1674. 使数组互补的最少操作数
class Solution:
def minMoves(self, nums: List[int], limit: int) -> int:
diff = [0 for i in range(2*limit +2)]
n = len(nums)
for i in range(n//2):
A = nums[i]
B = nums[n-1-i]
l = 2
r = 2*limit
diff [l] +=2
diff[r+1] -=2
l = 1 + min(A,B)
r = limit + max(A,B)
diff [l] -=1
diff [r+1] +=1
diff [A+B] -=1
diff[A+B+1] +=1
print(diff)
res = n
sum_val = 0
for j in range(2,2+limit+1):
sum_val += diff[j]
res = min(res, sum_val)
return res
121. 买卖股票I
122. 买卖股票II
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/133434.html原文链接：https://javaforall.net
