leetcode 算法总结--差分数组
Sunny-lucking opened this issue · 0 comments
Sunny-lucking commented
总结
差分数组是一个与原来数组具有相等长度的数组,其第i个位置的值,表示原数组中第i个位置值减去原数组第i-1个位置的值。简而言之,缓存了原数组中相同索引元素与其上一个元素的差。
1109. 航班预订统计
这道题是非常典型的差分数组,解法非常规矩,建立一个差分数组就好了。
不过需要注意一点,就是在处理nums[right] -= 1
的时候,需要判断当前的right是否已经过n。
/**
* @param {number[][]} bookings
* @param {number} n
* @return {number[]}
*/
var corpFlightBookings = function(bookings, n) {
let nums = new Array(n).fill(0);
for(let i = 0; i < bookings.length; i++) {
const left = bookings[i][0] - 1;
const right = bookings[i][1];
nums[left] += bookings[i][2];
if(right < n) {
nums[right] -= bookings[i][2];
}
}
for(let i = 1; i < nums.length; i++) {
nums[i] += nums[i - 1];
}
return nums;
};
1450. 在既定时间做作业的学生人数
这道题可以用差分,但是似乎也没必要。
直接判断 处于startime 和 endtime 之间的数就好了。
/**
* @param {number[]} startTime
* @param {number[]} endTime
* @param {number} queryTime
* @return {number}
*/
var busyStudent = function(startTime, endTime, queryTime) {
const len = startTime.length;
let count = 0;
for(let i = 0; i < len; i++) {
if(startTime[i] <= queryTime && queryTime <= endTime[i]) {
count += 1
}
}
return count;
};
1094. 拼车
这道题也是用比较常规的差分数组来解决的。
需要注意的是,初始化数组时,可以给定个1001的长度,因为我们不知道right会是多大,但是不会超过1000.
/**
* @param {number[][]} trips
* @param {number} capacity
* @return {boolean}
*/
var carPooling = function(trips, capacity) {
let len = trips.length;
let sum = new Array(1001).fill(0);
for(let i = 0; i < len; i++) {
let left = trips[i][1];
let right = trips[i][2];
let num = trips[i][0];
sum[left] += num;
sum[right] -= num;
}
let count = 0
for(let i = 0; i < sum.length; i++) {
count += sum[i];
if(count > capacity) {
return false
}
}
return true;
};
731. 我的日程安排表 II
这道题需要利用map结构存储差分,而不是数组。
然后我们获取map的values,进行相加操作,相加过程如果发现和大于2,说明出现三重,则将本次添加的回退,然后返回false。
var MyCalendarTwo = function() {
this.map = {};
};
/**
* @param {number} start
* @param {number} end
* @return {boolean}
*/
MyCalendarTwo.prototype.book = function(start, end) {
this.map[start] = (this.map[start] ?? 0) + 1;
this.map[end] = (this.map[end] ?? 0) - 1;
const values = Object.values(this.map);
let count = 0;
for(let value of values) {
count+= value
if(count >= 3) {
this.map[start] -= 1
this.map[end] += 1
return false
}
}
return true;
};
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* var obj = new MyCalendarTwo()
* var param_1 = obj.book(start,end)
*/
732. 我的日程安排表 III
这道题解法跟上道类似,反而简单了些,因为不用回退操作了。
var MyCalendarThree = function() {
this.map = {};
};
/**
* @param {number} startTime
* @param {number} endTime
* @return {number}
*/
MyCalendarThree.prototype.book = function(startTime, endTime) {
this.map[startTime] = (this.map[startTime] ?? 0) + 1;
this.map[endTime] = (this.map[endTime] ?? 0) - 1;
const values = Object.values(this.map);
let count = 0;
let max = 0;
for(let value of values) {
count+= value
max = Math.max(count, max);
}
return max;
};
/**
* Your MyCalendarThree object will be instantiated and called as such:
* var obj = new MyCalendarThree()
* var param_1 = obj.book(startTime,endTime)
*/
1854. 人口最多的年份
这道题跟上面的类似,不写了。
370. 区间加法
解法跟航班的类似,没有会员,不写了。
欢迎去我的github查看更多文章
github:https://github.com/Sunny-lucking