免费商城自助建站,个人cms网站,wordpress 文章插件,专业的大连网站建设前缀和技巧 针对的算法场景是不需要对原始数组进行修改的情况下#xff0c;频繁查询某个区间的累加和。 差分数组 主要适用场景是频繁对原始数组的某个区间的元素进行增减。
相关题目 1094. 拼车 1109. 航班预订统计 370. 区间加法
# 1094. 拼车
class Solution:def carPool…前缀和技巧 针对的算法场景是不需要对原始数组进行修改的情况下频繁查询某个区间的累加和。 差分数组 主要适用场景是频繁对原始数组的某个区间的元素进行增减。
相关题目 1094. 拼车 1109. 航班预订统计 370. 区间加法
# 1094. 拼车
class Solution:def carPooling(self, trips: List[List[int]], capacity: int) - bool:nums [0]*1000df Difference(nums)for trip in trips:df.increment(trip[1], trip[2]-1, trip[0])res df.restore()for need in res:if need capacity:return Falsereturn Trueclass Difference:def __init__(self, nums):assert len(nums)0self.diff [None]*len(nums)self.diff[0] nums[0]for i in range(1, len(nums)):self.diff[i] nums[i] - nums[i-1]# 给闭区间 [i, j] 增加 val可以是负数def increment(self, i, j, val):self.diff[i] valif j 1 len(self.diff):self.diff[j1] - val# 根据差分数组还原结果def restore(self):self.res [None]*len(self.diff)self.res[0] self.diff[0]for i in range(1, len(self.diff)):self.res[i] self.res[i-1] self.diff[i]return self.res
# 1109. 航班预订统计
class Solution:def corpFlightBookings(self, bookings: List[List[int]], n: int) - List[int]:nums [0]*ndf Difference(nums)for booking in bookings:df.increment(booking[0]-1, booking[1]-1, booking[2])return df.restore()class Difference:def __init__(self, nums):assert len(nums)0self.diff [None]*len(nums)self.diff[0] nums[0]for i in range(1, len(nums)):self.diff[i] nums[i] - nums[i-1]# 给闭区间 [i, j] 增加 val可以是负数def increment(self, i, j, val):self.diff[i] valif j 1 len(self.diff):self.diff[j1] - val# 根据差分数组还原结果def restore(self):self.res [None]*len(self.diff)self.res[0] self.diff[0]for i in range(1, len(self.diff)):self.res[i] self.res[i-1] self.diff[i]return self.res
