备战蓝桥杯————差分数组2
引言
在现代交通管理中，拼车服务和航班预订系统是提高资源利用效率、优化用户体验的关键技术。随着城市交通压力的增大和航空业的快速发展，如何有效地处理这些系统的动态变化，成为了算法工程师们面临的挑战。本文将探讨两个典型的算法问题：拼车服务中的车辆容量优化和航班预订统计。我们将通过差分数组这一高效的算法技巧，来解决这些实际问题，展示如何用智慧的算法为现代交通系统注入活力。
一、拼车
题目描述
车上最初有
capacity个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）给定整数capacity和一个数组trips,trip[i] = [numPassengersi, fromi, toi]表示第i次旅行有numPassengersi乘客，接他们和放他们的位置分别是fromi和toi。这些位置是从汽车的初始位置向东的公里数。当且仅当你可以在所有给定的行程中接送所有乘客时，返回true，否则请返回false。
示例 1：
输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false示例 2：
输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true提示：
1 <= trips.length <= 1000trips[i].length == 31 <= numPassengersi <= 1000 <= fromi < toi <= 10001 <= capacity <= 105
解题思路及代码
这道题我们看到区间及每个区间上的乘客数可以想到使用差分数组，计算每个路段的上车人数，再将计算的数组与容量比较，如果数组的最大值小于容量，返回true，如果不是返回false。需要注意的是，在使用下面代码进行比较时，虽然在还原数组时比较少了一个循环，但需要把num[0]也进行比较。
class Solution {
public int[] diff;
public int[] res;
public boolean carPooling(int[][] trips, int capacity) {
diff=new int[1001];
for(int[] i:trips ){
increment(i[1],i[2]-1,i[0]);
}
return result(capacity);
}
public void increment(int a,int b,int val){
diff[a]+=val;
if(b+1<diff.length)diff[b+1]-=val;
}
public boolean result(int capacity){
res=new int[1001];
res[0]=diff[0];
for(int i=1;i<diff.length;i++){
res[i]=res[i-1]+diff[i];
if(res[i]>capacity)return false;
}
if(res[0]>capacity)return false;
return true;
}
}结果展示
二、航班预定统计
题目描述
这里有
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]提示：
1 <= n <= 2 * 1041 <= bookings.length <= 2 * 104bookings[i].length == 31 <= firsti <= lasti <= n1 <= seatsi <= 104
解题思路及代码
其实它就是个差分数组的题，题目翻译一下就是：给你输入一个长度为
n的数组nums，其中所有元素都是 0。再给你输入一个bookings，里面是若干三元组(i, j, k)，每个三元组的含义就是要求你给nums数组的闭区间[i-1,j-1]中所有元素都加上k。请你返回最后的nums数组是多少？因为题目说的n是从 1 开始计数的，而数组索引从 0 开始，所以对于输入的三元组(i, j, k)，数组区间应该对应[i-1,j-1]。
class Solution {
int diff[];
int res[];
int num[];
public int[] corpFlightBookings(int[][] bookings, int n) {
num=new int[n];
diff=new int[n];
res=new int[n];
for(int[] i:bookings){
increment(i[0]-1,i[1]-1,i[2]);
}
res[0]=diff[0];
for(int i=1;i<n;i++){
res[i]=res[i-1]+diff[i];
}
return res;
}
public void increment(int i,int j,int val){
diff[i]+=val;
if(j+1<diff.length)diff[j+1]-=val;
}
}结果展示
总结
通过本文的分析和实现，我们不仅掌握了差分数组这一强大的算法工具，还学会了如何将其应用于解决实际的交通管理问题。无论是拼车服务中的车辆容量计算，还是航班预订统计，差分数组都以其简洁高效的处理方式，展现了算法的魅力。在技术日益发展的今天，算法不仅是解决问题的手段，更是推动社会进步的重要力量。让我们继续探索算法的深度与广度，用科技的力量为人类的生活带来更多可能。
腾讯云开发者
