1109. 航班预订统计 | 差分数组

# CODE

• Time Limit Exceeded
``````class Solution:
def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
# 结果初始化
result = []
for i in range(n):
result.append(0)

for m in range(bookings.__len__()):
diff = self.diffList(result,bookings[m][0],bookings[m][1],bookings[m][2])

result[0] = diff[0]
for n in range(len(result) - 1):
result[n + 1] = result[n] + diff[n+1]

return result

# 差分数组更新方法
# m 对应dif 的 m - 1
def diffList(self,inputList,m,n,add):

# 差分数组构造
dif = [inputList[0]]
for i in range(len(inputList) - 1):
dif.append(inputList[i+1] - inputList[i])

dif[m - 1] += add

if n != len(inputList):
dif[n] -= add

return dif
``````
• Accept

``````class Solution4:
def corpFlightBookings(self, bookings, n):
# 创造一个初始结果list
f = [0 for _ in range(n)]
print(f)

for s, e, diff in bookings:
print("s " + str(s) + "\te " + str(e) + "\tdiff " + str(diff))
# 这里是为了我们常规理解的位置和list位置相对应
s -= 1
e -= 1

# 差分数组只更改了区间端口的两个值
# 先构造了完整的差分数组
# 没有新建，在原值上进行了更新，优化了存储空间
# 谁说了差分数组只能新建一个的？新建可能容易理解一些
# 开始改变的端口
f[s] += diff
# 这里是为了避免改变有可能到最后一个也需要改变的情况
if e + 1 < n:
# 撤销改变
f[e + 1] -= diff
print(f)
print("------------------------------------------")

# 再用差分数组对结果值进行反推
for i in range(1, n):
print(i)
print(f)
f[i] += f[i - 1]
print('-------------------')
return f

S4 = Solution4()
booking = [[1,2,10],[2,3,20],[2,5,25],[5,5,15],[2,2,3]]
n = 5
result = str(S4.corpFlightBookings(booking,n))
print("##################################")
print(result)
``````

### 要不赞赏一下?

 微信 支付宝 PayPal Bitcoin

``https://www.emperinter.info/2022/02/17/corporate-flight-bookings/``

## 优惠码

 阿里云国际版 20美元 Vultr 10美元 搬瓦工 | Bandwagon 应该有折扣吧？ Just My Socks JMS9272283 【注意手动复制去跳转】 域名 | namesilo `emperinter`(1美元) 币安 币安