Home Page

题目描述

官方描述(中文)
2021/08/31每日一题

思路

这道题目用到了前缀和+差分数组。差分数组介绍, 对于一个预定区间预定的座位数是相同的，也就是对于原数组[i, j]区间同时加预定座位数，而这个条件完美的符合了差分数组的作用。

1. 新建一个大小为n的数组A，数组内的数字都为0；
2. 求数组A的差分数组B，显然A的差分数组就是A。为了方便区分将其命名为B，实际上B就是A。
3. 对于区间[i,j]，B[i-1]+=addNum, B[j]-=addNum.
4. 最后对B求取前缀和数组，得到的就是统计列表

代码

class Solution 
{
public:
	vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) 
	{
		vector<int>res(n, 0);
		for (const auto& iter : bookings)
		{
			if (iter.size() < 3)continue;
			res[iter[0] - 1] += iter[2];
			if (iter[1] < n)
			{
				res[iter[1]] -= iter[2];
			}
		}
		for (auto i = 1; i < res.size(); ++i)
		{
			res[i] += res[i - 1];
		}
		return res;
	}
};

运行结果

Q.E.D.