leetcode:1109航班预定统计
1109航班预定统计
-
- 题目描述
- 解题文案
题目描述
这里有 n 个航班,它们分别从 1 到 n 进行编号。
我们这儿有一份航班预订表,表中第 i 条预订记录 bookings[i] = [j, k, l] 意味着我们在从 j 到 k 的每个航班上预订了 l 个座位。
请你返回一个长度为 n 的数组 answer,按航班编号顺序返回每个航班上预订的座位数。
实例:
输入:bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5输出:[10,55,45,25,25]
提示:
1 <= bookings.length <= 200001 <= bookings[i][0] <= bookings[i][1] <= n <= 200001 <= bookings[i][2] <= 10000
主要用到的差分序列,
解题文案
主要用到的差分序列(详情其他博客写的),
这里做一个与树状数组的比较:
差分序列 | 树状数组 | |
---|---|---|
场景使用 | 区间加,单点查询 | 单点加 区间查询 |
代码实现
class Solution: def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]: res = [0] * (n + 1) for j, k, l in bookings: res[j-1] += l res[k] -= l for i in range(1, len(res)): res[i] += res[i-1] return res[:-1]
创作打卡挑战赛 赢取流量/现金/CSDN周边激励大奖