leetcode 算法总结--差分数组

[Sunny-lucking]

• 1109. 航班预订统计
• 1450. 在既定时间做作业的学生人数
• 1094. 拼车
• 731. 我的日程安排表 II
• 732. 我的日程安排表 III
• 1854. 人口最多的年份
• 370. 区间加法

总结

差分数组是一个与原来数组具有相等长度的数组，其第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