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

1109. 航班预订统计

• 差分数组技巧适⽤于频繁对数组区间进⾏增减的场景
  $$1.由数组a生成差分数组b\{\begin{array}{l}b[0]=0,i=0(或者b[0]=a[0],i=0)\\ b[i]=a[i]-a[i-1],i>0\end{array}$$

$$2.进⾏区间增减，若想对区间[i,j]的元素全部加3，\{\begin{array}{l}b[i]+=3\\ b[j+1]-=3\end{array}$$

$$3.还原$$

c[0] = a[0];
for (int i = 1; i < b.size(); i++) {c[i] = c[i - 1] + b[i];
}

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/corporate-flight-bookings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 此问题对应的初始数组为全o数组。

#include <stdio.h>
#include <algorithm>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;class Solution {
public:vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {vector<int> nums(n);for (auto& booking : bookings) {nums[booking[0] - 1] += booking[2];// 注意转成数组索引要减⼀if (booking[1] < n) {nums[booking[1]] -= booking[2];}}for (int i = 1; i < n; i++) {nums[i] += nums[i - 1];}return nums;}};int main()
{Solution *myslo = new Solution();vector<vector<int>> v1 = {{1,2,10},{2,3,20},{2,5,25}}; int n=5;vector<int> res = myslo->corpFlightBookings(v1,n);cout<<"res_output"<<endl;for(auto v:res)cout<< v<<endl;delete myslo;return 0;
}

CG

• 370. 区间加法