深圳专业做网站和seo的公司,html做的网页怎么变成网站,大型网站建设企业名录模板,网站建设功能怎么写力扣labuladong一刷day18天差分数组 文章目录 力扣labuladong一刷day18天差分数组一、370. 区间加法二、1109. 航班预订统计三、1094. 拼车 一、370. 区间加法
题目链接#xff1a;https://leetcode.cn/problems/range-addition/ 思路#xff1a;这种频繁改变数组的值#…力扣labuladong一刷day18天差分数组 文章目录 力扣labuladong一刷day18天差分数组一、370. 区间加法二、1109. 航班预订统计三、1094. 拼车 一、370. 区间加法
题目链接https://leetcode.cn/problems/range-addition/ 思路这种频繁改变数组的值最后在问数组中的值都是多少的情况特别适合使用查分数组所谓查分数组就是数组中每一个位置的值都等于原数组相邻位置相减的值即diff[0]nums[0]diff[i] nums[i]-nums[i-1]。 如nums [a, b, c, d] diff [a, b-a, c-b, d-c] 这样如果对区间[i, j] 加val只需要对差分数组diff进行 diff[i]val diff[j1]-val。即可这样不管做多少次的区间加值只需要对区间首尾进行操作时间复杂度就降低了。 那如何从差分数组还原回正常数组呢只需要res[0]diff[0]res[i] res[i-1]diff[i]。res定义为正常数组上面的地推公式就相当于把每个位置减掉的前一个位置的值又加了回来。 int[] getModifiedArray(int length, int[][] updates) {int[] nums new int[length];Difference difference new Difference(nums);for (int[] update : updates) {difference.increment(update[0], update[1], update[2]);}return difference.result();}
class Difference {int[] diff;// 构造查分数组public Difference(int[] nums) {diff new int[nums.length];diff[0] nums[0];for (int i 1; i diff.length; i) {diff[i] nums[i] - nums[i-1];}}void increment(int i, int j, int val) {diff[i] val;if (j1 diff.length) {diff[j1] - val;}}int[] result() {int[] nums new int[diff.length];nums[0] diff[0];for (int i 1; i diff.length; i) {nums[i] nums[i-1]diff[i];}return nums;}
}二、1109. 航班预订统计
题目链接https://leetcode.cn/problems/corporate-flight-bookings/ 思路思路和上一题一样就是差分数组。
class Solution {public int[] corpFlightBookings(int[][] bookings, int n) {int[] nums new int[n];Difference difference new Difference(nums);for (int[] book : bookings) {difference.sum(book[0]-1, book[1]-1, book[2]);}return difference.result();}
}class Difference {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];}}void sum(int i, int j, int val) {diff[i] val;if (j1 diff.length) {diff[j1] - val;}}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. 拼车
题目链接https://leetcode.cn/problems/car-pooling/ 思路这个拼车也是典型的差分数组的应用场景区间[i, j]表示从i上a个人到 j 下来。其实不用考虑上下人的问题就是把全部的区间都叠加到一起叠加的部分都是在车上的只要有一个地方大于容量即false。
class Solution {public boolean carPooling(int[][] trips, int capacity) {Difference difference new Difference();for (int[] trip : trips) {difference.sum(trip[1], trip[2], trip[0]);}int[] result difference.result();for (int i : result) {if (i capacity) return false;}return true;}
}class Difference {int[] diff new int[1001];void sum(int i, int j, int val) {diff[i] val;if (j 1 diff.length) {diff[j] - val;}}int[] result() {int[] res new int[diff.length];res[0] diff[0];for (int i 1; i res.length; i) {res[i] res[i-1] diff[i];}return res;}
}
