【小f的刷题笔记】（JS）数组 - 差分数组 LeetCode1109 & LeetCode1094

【数组】

差分数组：

🌟 频繁对原始数组的某个区间的元素进⾏增减

✔ 把每个数与前一个数的差值计算出来存在一个新数组里，区间的加减通过把新数组中区间开始下标的值加/减，区间结束下标对应的值减/加（反一下，因为最后每个数都是通过前一个值得出的）

---

LeetCode1109

链接：

1109.航班预订统计

题目：

思路：

-> 就是先定义一个差值数组，所有加的操作先在差值数组中进行，再利用这个差值数组通过第一项，继续推出后面的所有数

代码：

/**
 * @param {number[][]} bookings
 * @param {number} n
 * @return {number[]}
 */
var corpFlightBookings = function(bookings, n) {
    // 现将nums数组全部赋初值为0
    const nums = new Array(n).fill(0);
    // for-of 数组遍历元素， for-in对象遍历属性
    for(const booking of bookings) {
        nums[booking[0]-1] += booking[2];
        // 后面的值不是最后一个数，就得减
        if(booking[1]<n) {
            nums[booking[1]] -= booking[2];
        }
    }
    for(let i=1; i<n; i++) {
        nums[i] += nums[i-1];
    }
    return nums;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

LeetCode1094

链接：

1094.拼车

题目：

思路：

先定义一个差值数组，所有加减操作先在差值数组中进行，再利用这个差值数组通过第一项，继续推出后面的所有数，只要所有元素都比capacity小就行

注意点：

1️⃣ const

​ const声明的变量，不可以修改

​ const声明的数组，数组的元素是可以修改的

​ const声明的对象，对象的属性也是可以修改的

2️⃣ 新建数组

const 数组名 = new Array(数组长度).fill(初值);

3️⃣ [].every(条件)

​ 返回的是boolean

代码：

/**
 * @param {number[][]} trips
 * @param {number} capacity
 * @return {boolean}
 */
var carPooling = function(trips, capacity) {
    // 构建差值数组
    const diff = new Array(1001).fill(0)
    for(const trip of trips) {
        diff[trip[1]] += trip[0]
        diff[trip[2]] -= trip[0] // 这里第三个数是已经放下乘客的位置了，所以直接用下标，不用+1
    }

    // 这里的另一种写法 已知trips数组元素的格式了，就可以直接定义这样的数组，拿数据稍微方便点儿
    // 解构
    // for(const [n, s, e] of trips) {
    //     diff[s] += n
    //     diff[e] -= n
    // }

    let sum = 0
    // 遍历一遍差值数组，算出每个站的乘客数，与capacity比较
    for(let i=0; i<diff.length; i++) {
        sum += diff[i]
        if(sum > capacity) return false
    }
    return true
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

---

写在最后：
labuladong写得真的好好呀
思路写得比较口语化，之后慢慢改进
还在摸索阶段，加油叭！