18成禁人养成游戏手游,网站优化一般怎么做,银行网站建设前期合同,网站建设分金手指专业十二提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言差分数组工具类一、力扣370. 区间加法二、力扣1109. 航班预订统计三、力扣1094. 拼车 前言
差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言差分数组工具类一、力扣370. 区间加法二、力扣1109. 航班预订统计三、力扣1094. 拼车 前言
差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减 这里提供一个工具类方便大家使用 差分数组工具类
class Difference{private int[] diff;public Difference(int[] nums){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 increment(int low, int high, int val){diff[low] val;if(high diff.length-1){diff[high1] - 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;}
}一、力扣370. 区间加法
class Solution {public int[] getModifiedArray(int length, int[][] updates) {int[] res new int[length];Difference diff new Difference(res);for(int i 0; i updates.length; i ){diff.increment(updates[i][0],updates[i][1],updates[i][2]);}res diff.result();return res;}
}
class Difference{private int[] diff;public Difference(int[] nums){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 increment(int low, int high, int val){diff[low] val;if(high diff.length-1){diff[high1] - 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;}
}二、力扣1109. 航班预订统计
class Solution {public int[] corpFlightBookings(int[][] bookings, int n) {int[] res new int[n];Difference diff new Difference(res);for(int i 0; i bookings.length; i ){diff.increase(bookings[i][0]-1,bookings[i][1]-1,bookings[i][2]);}res diff.result();return res;}
}
class Difference{private int[] diff;public Difference(int[] nums){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 increase(int low,int high, int val){diff[low] val;if(high 1 diff.length){diff[high1] - 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;}
}三、力扣1094. 拼车
class Solution {public boolean carPooling(int[][] trips, int capacity) {int[] res new int[1001];Difference diff new Difference(res);for(int i 0; i trips.length; i ){diff.increase(trips[i][1],trips[i][2]-1,trips[i][0]);}res diff.result();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){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 increase(int low, int high, int val){diff[low] val;if(high 1 diff.length){diff[high1] - 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;}
}
