大家好,又见面了,我是你们的朋友全栈君。
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
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/133434.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...