差分数组技巧
数组 技巧 差分
2023-06-13 09:11:45 时间
大家好,又见面了,我是你们的朋友全栈君。
差分数组技巧
一、差分数组适用题型,和技巧
- 前缀和数组:适用于原始数组不会被修改的情况下,频繁查询某个区间的累加和
- 差分数组:主要适⽤场景是频繁对原始数组的某个区间的元素进⾏增减(比如:给你和数组arr,然后再下标0-4之间各元素加一,2-5之间各个元素减2,求最终的原数组)
- 差分数组技巧 1.构建差分数组(diff),diff[0]=nums[0],之后diff[i]=nums[i]-nums[i-1]
int[] diff = new int[nums.length];
// 构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
2.根据差分树组反推原数组(res):res[0]=diff[0],res[i]=res[i-1]+diff[i]
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];
}
3.这样构造差分数组 diff,就可以快速进⾏区间增减的操作,如果你想对区间 nums[i…j] 的元素全部加3,那么只需要让 diff[i] += 3,然后再让 diff[j+1] -= 3 即可:
- 构建差分数组类
// 差分数组⼯具类
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];
}
}
/* 给闭区间 [i,j] 增加 val(可以是负数)*/
public void increment(int i, int j, int val) {
diff[i] += val;
if (j + 1 < diff.length) {
diff[j + 1] -= val;
}
}
/* 返回结果数组 */
public int[] result() {
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;
}
}
二、区间加法
- 解题: 1.只需将差分数组类导入 2.在编写以下代码:
int[] getModifiedArray(int length, int[][] updates) {
// nums 初始化为全 0
int[] nums = new int[length];
// 构造差分解法
Difference df = new Difference(nums);
for (int[] update : updates) {
int i = update[0];
int j = update[1];
int val = update[2];
df.increment(i, j, val);
}
return df.result();
}
三、航班预订系统
- 分析: 1.给你输⼊⼀个⻓度为 n 的数组 nums,其中所有元素都是 0。再给你输⼊⼀个 bookings,⾥⾯是若⼲三元组(i,j,k),每个三元组的含义就是要求你给 nums 数组的闭区间 [i-1,j-1] 中所有元素都加上 k。请你返回最后的 nums 数组是多少? 2.题目说座位是从1开始的,但差分树组是从0开始的所以这里的i,j都得-1.
- 解题: 1.只需将差分数组类导入 2.在编写以下代码:
// 差分数组⼯具类
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];
}
}
/* 给闭区间 [i,j] 增加 val(可以是负数)*/
public void increment(int i, int j, int val) {
diff[i]+=val;
if(j+1<diff.length){
diff[j+1]-=val;
}
}
public int[] reslut(){
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;
}
}
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int nums[]=new int [n];
Difference df=new Difference(nums);
for(int arr[]:bookings){
int i=arr[0]-1;
int j=arr[1]-1;
int val=arr[2];
df.increment(i,j,val);
}
return df.reslut();
}
}
- 优化: 1.没有导入数据之前所有数据都是0,所以num[s]=new int[n],将nums看成差分树组,然后遍历航班信息 2.最后再根据差分数组返回结果
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int nums[]=new int [n];
for(int arr[]:bookings){
int i=arr[0]-1;
int j=arr[1]-1;
int val=arr[2];
nums[i]+=val;
if(j+1<n){
nums[j+1]-=val;
}
}
for (int i = 1; i < n; i++) {
nums[i] += nums[i - 1];
}
return nums;
}
}
四、拼车
- 分析: 1.trips[i] 代表着⼀组区间操作,旅客的上⻋和下⻋就相当于数组的区间加减;只要结果数组中的元素都⼩于 capacity,就说明可以不超载运输所有旅客。 2.第j站时旅客已经下车了则,j要减1 3.差分树组的大小为站的个数可以自己写函数算 4.构建完差分年数组,在反推原结果时可以顺便比较与车乘载人数capacity相比较(因为for循环是从i开始的,第一次上车人数超过时需要重新考虑)
- 解题:
class Solution {
public boolean carPooling(int[][] trips, int capacity) {
int max=0;
//计算此次中到达最远的栈的编号
for(int[] trip : trips){
max = Math.max(trip[2], max);
}
//nums看做差分数组
int nums[]=new int [max];
//遍历信息 构建差分树组
for(int trip[]:trips){
int val=trip[0];
//处理第一次人数大于乘载量的情况
if(capacity<val)
return false;
//路程是trip[1]-trip[2]-1
int i=trip[1];
int j=trip[2]-1;
nums[i]+=val;
if(j+1<max){
nums[j+1]-=val;
}
}
//各个
int res[]=new int[max];
res[0]=nums[0];
for(int i=1;i<max;i++){
res[i]=nums[i]+res[i-1];
if(res[i]>capacity) return false;
}
return true;
}
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/140603.html原文链接:https://javaforall.cn
相关文章
- 数组转换成list集合_字符串转数组js
- Java 数组、排序和查找(1)
- Java输出数组的内容「建议收藏」
- VBA技巧:使用数组复制不同的列
- Excel公式技巧:颠倒单元格区域/数组
- split拆分数组长度问题详解编程语言
- Java数据结构和算法(二)——数组详解编程语言
- 寻找两个有序数组的中位数算法详解编程语言
- Linux下实现二维数组的技巧(linux二维数组)
- MySQL中使用数组字段的技巧(mysql数组字段类型)
- Oracle中管理字符串数组的技巧(oracle字符串数组)
- MySQL中使用变量数组的技巧(mysql变量数组)
- 「MongoDB技巧解密」:快速精确实现数组查询(mongodb数组查询)
- MongoDB数组修改技巧(mongodb修改数组)
- MySQL数组变量定义技巧探索”(mysql数组变量定义)
- Linux实现数组快速赋值技巧(linux数组赋值)
- javascript中的array数组使用技巧
- Oracle定义联合数组及使用技巧
- vb.net数组参与SQL语句的查询范例
- 在JS数组特定索引处指定位置插入元素的技巧