前言

最近leetcode的每日刷題都是前綴和類的窿凤，比較有連貫性仅偎。沒(méi)有上來(lái)搞個(gè)hard打擊人跨蟹。本題用到了差分、前綴和橘沥，好記性不爛筆頭窗轩，筆記之。歡迎點(diǎn)贊????

這里有 n 個(gè)航班座咆，它們分別從 1 到 n 進(jìn)行編號(hào)痢艺。

有一份航班預(yù)訂表 bookings ，表中第 i 條預(yù)訂記錄 bookings[i] = [firsti, lasti, seatsi] 意味著在從 firsti 到 lasti （包含 firsti 和 lasti ）的 每個(gè)航班 上預(yù)訂了 seatsi 個(gè)座位介陶。

請(qǐng)你返回一個(gè)長(zhǎng)度為 n 的數(shù)組 answer堤舒，其中 answer[i] 是航班 i 上預(yù)訂的座位總數(shù)。

來(lái)源：力扣（LeetCode）

鏈接：https://leetcode-cn.com/problems/corporate-flight-bookings

示例 1：

輸入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5

輸出：[10,55,45,25,25]

解釋：

航班編號(hào) 1 2 3 4 5

預(yù)訂記錄 1 ： 10 10

預(yù)訂記錄 2 ： 20 20

預(yù)訂記錄 3 ： 25 25 25 25

總座位數(shù)： 10 55 45 25 25

因此哺呜，answer = [10,55,45,25,25]

1 <= n <= 2 * 104

1 <= bookings.length <= 2 * 104

bookings[i].length == 3

1 <= firsti <= lasti <= n

1 <= seatsi <= 104

讀題

1. 有n個(gè)航班舌缤，起始位置是1。

2. bookings[i] = [startSeats, ensSeats, seats]表示從 startSeats 到 ensSeats （包含 firsti 和 lasti ）的每個(gè)航班上預(yù)訂 seatsi 個(gè)座位。

要求：返回一個(gè)數(shù)組国撵，里面的元素是每個(gè)航班預(yù)定的座位數(shù)陵吸。

解題

看這個(gè)題，直觀的思維就是一個(gè)一個(gè)遍歷bookings介牙。然后去累加每一個(gè)booking[2]壮虫。但是這樣會(huì)超時(shí)。

那我們把題例簡(jiǎn)化下: bookings = [[1, 2 , 10]]; n = 5;

就變成了

插一句环础，首先了解一個(gè)概念囚似，什么是差分?jǐn)?shù)組？

差分?jǐn)?shù)組：對(duì)應(yīng)的概念是前綴和數(shù)組线得。例如[1, 2, 3, 4]的前綴和結(jié)果就是[1, 3, 6, 10]谆构， 其差分?jǐn)?shù)組就是[1, 1, 1, 1]。

ok繼續(xù)框都，如果我們只標(biāo)記1和3呢搬素？

所以就可以轉(zhuǎn)換為標(biāo)記1到3這個(gè)區(qū)間，增量10魏保。只需要操作這個(gè)區(qū)間的兩端熬尺，區(qū)間左端加10， 區(qū)間右端+1位置-10谓罗。之后其他區(qū)間也這么標(biāo)記粱哼。構(gòu)造差分?jǐn)?shù)組，再依據(jù)差分?jǐn)?shù)組計(jì)算前綴和就可以得到題目想要的結(jié)果檩咱。即采用差分的思想來(lái)模擬區(qū)間的增量揭措。

再回到本題示例bookings = [[1, 2, 10], [2, 3, 20], [2, 5, 25]]; n = 5

WeChat81e64f69bbef4a46a672bde73fbe0e00

代碼

個(gè)人題解

暴力法(超時(shí))

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> res(n);

        for (auto &b : bookings) {
            for (int i = b[0] - 1; i < b[1]; i++) {
                res[i] += b[2];
            }
        }
        return res;
    }
};

差分、前綴和

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> res(n + 1);
        int l = 0, r = 0, a = 0;
        for (auto & b : bookings) {
            l = b[0] - 1;
            r = b[1] - 1;
            a = b[2];
            res[l] += a;
            res[r + 1] -= a;
        }
        vector<int> fCount(n);

        for (int i = 0; i < n; i++) {
            if (i == 0) {
                fCount[i] = res[0];
            }else {
                fCount[i] = fCount[i - 1] + res[i];
            }
        }
        return fCount;
    }
};

官方題解

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> nums(n);
        for (auto& booking : bookings) {
            nums[booking[0] - 1] += booking[2];
            if (booking[1] < n) {
                nums[booking[1]] -= booking[2];
            }
        }
        for (int i = 1; i < n; i++) {
            nums[i] += nums[i - 1];
        }
        return nums;
    }
};

其他

其他算法詳細(xì)題解