参阅基础

简介

适用场景：频繁对原始数组的某个区间的元素进行增减。

差分数组抽象类

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
29
class Difference {
    constructor(nums) {
        this.diff = new Array(nums.length).fill(0);
        this.diff[0] = nums[0];
        for (let i = 1; i <= nums.length - 1; i++) {
            this.diff[i] = nums[i] - nums[i - 1];
        }
    }

 // 让用户去执行区间加减操作
    increment(i, j, val) {
        this.diff[i] += val;
        if (this.diff[j + 1] < this.diff.length) {
            this.diff[j + 1] -= val;
        }
        console.log(this.diff);
    }

 // 将差分数组转换为结果数组
    result() {
        const res = new Array(this.diff.length).fill(0);
        res[0] = this.diff[0];
        for (let i = 1; i <= res.length - 1; i++) {
            res[i] = res[i - 1] + this.diff[i];
        }

        return res;
    }
}

相关习题

Leetcode 370. 区分加法

题目

假设你有一个长度为n的数组，初始情况下所有的数字均为0，你将会被给出k个更新的操作。

其中，每个操作会被表示为一个三元组：**[startIndex,endIndex,inc]，你需要将子数组A[startIndex…endIndex]（包括startIndex和endIndex）增加inc**

请你返回k次操作后的数组。

示例：

输入：length = 5，updates = [[1,3,2],[2,4,3],[0,2,-2]]

输出：[-2,0,3,5,3]

解释：

初始状态：[0,0,0,0,0]

进行了操作 [1,3,2] 后的状态：[0,2,2,2,0]

进行了操作 [2,4,3] 后的状态：[0,2,5,5,3]

进行了操作 [0,2,-2] 后的状态：[-2,0,3,5,3]

来源：370. 区间加法🔒

我的题解

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
const getModifiedArray = (numsArrOrLen, updates) => {
    if (typeof numsArrOrLen === "number") {
        numsArrOrLen = new Array(numsArrOrLen).fill(0);
        console.log(numsArrOrLen);
    }

    //使用差分数组抽象类
    const df = new Difference(numsArrOrLen);

    for (update of updates) {
        let i = update[0];
        let j = update[1];
        let val = update[2];
        df.increment(i, j, val);
    }

    return df.result();
};

console.log(
    getModifiedArray(
        [2, 5, 9, 1, 0, 50],
        [
            [1, 2, 6],
            [1, 2, -6],
        ]
    )
);

Leetcode 1094. 拼车

题目

车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）

给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

输入 1:

1
2
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

输入 2:

1
2
Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true

提示

  • 1 <= trips.length <= 1000
  • trips[i].length == 3
  • 1 <= numPassengersi <= 100
  • 0 <= fromi < toi <= 1000
  • 1 <= capacity <= 105

来源：1094. 拼车

我的题解

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
//拼车
const carPooling = (trips, capacity) => {
    let coachNum = new Array(1001).fill(0);
    let df = new Difference(coachNum);

    trips.forEach((trip) => {
        let startStation = trip[1];
        let endStation = trip[2] - 1;
        let numPassengers = trip[0];
        df.increment(startStation, endStation, numPassengers);
    });

    const procedures = df.result();
    console.log(procedures);

    return procedures.every((station) => station <= capacity);
};

console.log(
    carPooling(
    [
        [2, 1, 5],
        [3, 3, 7],
    ],
    5
    )
);

Leetcode 1109. 航班预订统计

题目

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

来源：Leetcode 1109. 航班预订统计

我的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 航班预定
const corpflightBookings = (bookings, num) => {
    let numsArr = new Array(num).fill(0);
    let df = new Difference(numsArr);

    bookings.forEach((booking) => {
        df.increment(...booking);
    });

    return df.result();
};

console.log(
    corpflightBookings(
    [
        [1, 2, 10],
        [2, 3, 30],
        [2, 5, 25],
    ],
    5
    )
);