山东定制型网站建设推广,如何做网站的外部链接,做企业网站怎么收费的,鄞州区优秀营销型网站建设首选这里有 n 个航班#xff0c;它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings #xff0c;表中第 i 条预订记录 bookings[i] [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti #xff08;包含 firsti 和 lasti #xff09;的 每个航班 上预订了 seatsi 个座…这里有 n 个航班它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings 表中第 i 条预订记录 bookings[i] [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti 包含 firsti 和 lasti 的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer里面的元素是每个航班预定的座位总数。 示例 1
输入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]示例 2
输入bookings [[1,2,10],[2,2,15]], n 2
输出[10,25]
解释
航班编号 1 2
预订记录 1 10 10
预订记录 2 15
总座位数 10 25
因此answer [10,25]
这道题大多数朋友上来肯定是暴力就做但是还有一种比较好的方法是使用差分数组。本题比较困难的点在于大多数新手可能不太清楚什么是差分数组。
这里为什么要使用差分数组呢因为这里的预订记录实际上代表了一个区间的增量。我们的任务是将这些增量叠加得到答案。所以这里使用差分数组能更快的做出来答案。这里主要使用的是差分数组的性质d[i]arr[i]-arr[i-1]并且我们需要注意如何使用差分数组去求原始数组的某一个确定值如何判断改变某一个区间元素后再求得其新的差分数组
这里给出暴力和差分两种思路
//差分
class Solution {public int[] corpFlightBookings(int[][] bs, int n) {int[] c new int[n 1];for (int[] bo : bs) { //求差分数组int l bo[0] - 1, r bo[1] - 1, v bo[2];c[l] v; //l和l前一位元素的差改变c[r 1] - v; //r和r后一位的元素的差改变}int[] ans new int[n];ans[0] c[0];for (int i 1; i n; i) {ans[i] ans[i - 1] c[i];}return ans;}
}//暴力
class Solution {public int[] corpFlightBookings(int[][] bookings, int n) {int[] ans new int[n];for (int[] booking : bookings) {for (int i booking[0]; i booking[1]; i) {ans[i - 1] booking[2];}}return ans;}
}
