描述
这里有 n 个航班，它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。
思路
差分数组,注意差分数组的变化的临界值判断。
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)
