[数据结构与算法]Leetcode1109航班预定记录&Leetcode1094拼车（差分数组的应用）

差分数组工具类：

• 思路：定义一个长度为nums数组长度的差分数组diff[];该数组的第一个元素即diff[0]等于nums[0]；从第二个元素起，存放的每一个空间为num[i]-nums[i-1]的差值；

• 当求数组nums[]从第i个元素到第j个元素均增加val值时（val可正可负）；即等价于diff[i]+=val；且当j+1不超过差分数组长度时，diff[j+1]-=val;

• 最后，利用差分数组的原理，重新返回目标结果数组。

class Difference{
 ? ?private int[] diff;
?
 ? ?public Difference(int[] nums){
 ? ? ? ?assert nums.length>0;
 ? ? ? ?diff = new int[nums.length];
 ? ? ? ?diff[0] = nums[0];
?
 ? ? ? ?for(int i =1 ;i<nums.length;i++){
 ? ? ? ? ? ?diff[i]= nums[i]-nums[i-1];
 ? ? ?  }
 ?  }
?
 ? ?public void increasement(int i,int j, int val){
 ? ? ? ?diff[i]+=val;
 ? ? ? ?if(j+1<diff.length){
 ? ? ? ? ? ?diff[j+1]-=val;
 ? ? ?  }
?
 ?  }
?
 ? ?public int[] res(){
 ? ? ? ?int[] res = new int[diff.length];
 ? ? ? ?res[0]=diff[0];
 ? ? ? ?for(int i =1 ;i<diff.length;i++){
 ? ? ? ? ? ?res[i] = res[i-1]+diff[i];
 ? ? ?  }
 ? ? ? ?return res;
?
 ?  }

差分数组的应用：

Leetcode1109：航班预定统计

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

• 题目翻译：数组 answer里面的元素是每个航班预定的座位总数。初始状态，数组answer中的每个元素均为0；每条预定记录则为answer数组下标从fisti-1到lasti-1均增加了seatsi，求最后增加了预定记录的数组answer。

class Solution {
 ? ?public int[] corpFlightBookings(int[][] bookings, int n) {
 ? ? ? ?int[] nums = new int[n];
 ? ? ? ?Difference df = new ?Difference(nums);
 ? ? ? ?for(int[] booking:bookings){
 ? ? ? ? ? ?int i =booking[0]-1;
 ? ? ? ? ? ?int j = booking[1]-1;
 ? ? ? ? ? ?int val = booking[2];
 ? ? ? ? ? ?df.increasement(i,j,val);
 ? ? ?  } 
?
 ? ? ? ?return df.res();
 ?  }
?
 ? ?
}
?
class Difference{
 ? ?private int[] diff;
?
 ? ?public Difference(int[] nums){
 ? ? ? ?assert nums.length>0;
 ? ? ? ?diff = new int[nums.length];
 ? ? ? ?diff[0] = nums[0];
?
 ? ? ? ?for(int i =1 ;i<nums.length;i++){
 ? ? ? ? ? ?diff[i]= nums[i]-nums[i-1];
 ? ? ?  }
 ?  }
?
 ? ?public void increasement(int i,int j, int val){
 ? ? ? ?diff[i]+=val;
 ? ? ? ?if(j+1<diff.length){
 ? ? ? ? ? ?diff[j+1]-=val;
 ? ? ?  }
?
 ?  }
?
 ? ?public int[] res(){
 ? ? ? ?int[] res = new int[diff.length];
 ? ? ? ?res[0]=diff[0];
 ? ? ? ?for(int i =1 ;i<diff.length;i++){
 ? ? ? ? ? ?res[i] = res[i-1]+diff[i];
 ? ? ?  }
 ? ? ? ?return res;
?
 ?  }
}

Leetcode1094.拼车

题目：车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）

给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

class Solution {
 ? ?public boolean carPooling(int[][] trips, int capacity) {
 ? ? ? ?int[] nums = new int[1001];
 ? ? ? ?Difference df = new Difference(nums);
?
 ? ? ? ?for(int[] trip:trips){
 ? ? ? ? ? ?int val = trip[0];
 ? ? ? ? ? ?int i = trip[1];
 ? ? ? ? ? ?int j = trip[2]-1;
 ? ? ? ? ? ?df.increasement(i,j,val);
?
 ? ? ?  }
?
 ? ? ? ?int[] res = df.res();
 ? ? ? ?for(int i =0 ; i<res.length;i++){
 ? ? ? ? ? ?if(res[i]>capacity){
 ? ? ? ? ? ? ? ?return false;
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ? ?return true;
?
 ? ? ? ?
?
 ?  }
?
 ? ?class Difference{
?
 ? ? ? ?private int[] diff ;
?
 ? ? ? ?public Difference(int[] nums){
 ? ? ? ? ? ?assert nums.length>0;
 ? ? ? ? ? ?diff = new int[nums.length];
 ? ? ? ? ? ?diff[0]=nums[0];
 ? ? ? ? ? ?for(int i =1;i<nums.length;i++){
 ? ? ? ? ? ? ? ?diff[i] = nums[i] - nums[i-1];
 ? ? ? ? ?  }
?
 ? ? ?  }
?
 ? ? ? ?public void increasement(int i,int j ,int val){
 ? ? ? ? ? ?diff[i]+=val;
 ? ? ? ? ? ?if(j+1<diff.length){
 ? ? ? ? ? ? ? ?diff[j+1]-=val;
 ? ? ? ? ?  }
 ? ? ?  }
?
 ? ? ? ?public int[] res(){
 ? ? ? ? ? ?int[] res=new int[diff.length];
 ? ? ? ? ? ?res[0]=diff[0];
 ? ? ? ? ? ?for(int i =1;i<diff.length;i++){
 ? ? ? ? ? ? ? ?res[i] = res[i-1]+diff[i];
 ? ? ? ? ?  }
 ? ? ? ? ? ?return res;
?
 ? ? ?  }
 ?  }
}