diff 差分思维

这一系列的思路就是只记录init的值，之后全部记录变化量(diff).

370. Range Addition

i, j都是0-based. 直接上。注意stl partial_sum

class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        vector<int> df(length);
        for (const auto& u: updates) {
            int i = u[0], j = u[1], val = u[2];
            df[i] += val;
            if (j+1 < length) {
                df[j+1]-=val;
            }
        }
        partial_sum(df.begin(), df.end(), df.begin());
        return df;
    }
};

1109. Corporate Flight Bookings

这里注意输入是1 based，还是裸题

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> df(n, 0);
        for (auto& b: bookings) {
            int i = b[0] - 1, j = b[1] - 1, v = b[2];
            df[i] += v;
            if (j + 1< n) df[j + 1] -= v;
        }
        partial_sum(df.begin(), df.end(), df.begin());
        return df;
    }
};

1094. Car Pooling

这里很搞笑，没有告诉我range，没法初始化diff啊，直接按照最大的可能性初始化吧，哈哈。之后一样的题，只是找最大值是多少。

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        int n = 1001;
        vector<int> df(n);
        for (const auto& t: trips) {
            //passenger is at [i,j)
            int val = t[0], i = t[1], j = t[2]-1;
            df[i] += val;
            if (j + 1< n) {
                df[j + 1] -= val;
            }
        }
        partial_sum(df.begin(), df.end(), df.begin());
        return *max_element(df.begin(), df.end()) <= capacity;
    }
};

https://leetcode.com/problems/maximum-sum-obtained-of-any-permutation/

TODO

Written on December 28, 2021