编程-差分数组

本文主要是介绍编程-差分数组，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1893. 检查是否区域内所有整数都被覆盖

如果闭区间 [left, right] 内每个整数都被 ranges 中 至少一个 区间覆盖，那么请你返回 true ，否则返回 false 。

已知区间 ranges[i] = [starti, endi] ，如果整数 x 满足 starti <= x <= endi ，那么我们称整数x 被覆盖了。

示例 1：

输入：ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5
输出：true
解释：2 到 5 的每个整数都被覆盖了：
- 2 被第一个区间覆盖。
- 3 和 4 被第二个区间覆盖。
- 5 被第三个区间覆盖。

示例 2：

输入：ranges = [[1,10],[10,20]], left = 21, right = 21
输出：false
解释：21 没有被任何一个区间覆盖。

1094. 拼车

这儿有一份乘客行程计划表 trips[][]，其中 trips[i] = [num_passengers, start_location, end_location] 包含了第 i 组乘客的行程信息：

• 必须接送的乘客数量；
• 乘客的上车地点；
• 以及乘客的下车地点。

这些给出的地点位置是从你的 初始 出发位置向前行驶到这些地点所需的距离（它们一定在你的行驶方向上）。

请你根据给出的行程计划表和车子的座位数，来判断你的车是否可以顺利完成接送所有乘客的任务（当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false）。

示例 1：

输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false

示例 2：

输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true

示例 3：

输入：trips = [[2,1,5],[3,5,7]], capacity = 3
输出：true

示例 4：

输入：trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
输出：true

//map法
class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {

        set<int> s1;
        int i = 0;
        int tmp = 0;

        for (auto & e : trips) {
            s1.insert(e[1]);
            s1.insert(e[2]);
        }

        vector<int> v1(s1.size(), 0);
        unordered_map<int, int> m1;

        for (auto & e : s1) {
            m1.insert(pair<int, int>(e,i));
            i++;
        }

        for (auto & e : trips) {
            for (int j = m1.at(e.at(1)); j < m1.at(e.at(2)); ++j) {
                v1[j] += e.at(0);
            }
        }

        for (auto & e : v1) {
            tmp = max(tmp, e);
        }

        return tmp > capacity ? false : true;
    }
};

//差分+前缀和
class Solution {
    public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        // 存储所有地点的差分
        // endLocation坐标小于等于1000
        vector<int> diff(1001);
        for (auto & e : trips) {
            int num = e[0];
            int start = e[1];
            int end = e[2];
            diff[start] += num;
            diff[end] -= num;
        }

        int sum = 0;
        for (int i = 0; i < diff.size(); i++) {
            sum += diff[i];
            if (sum > capacity) {
                return false;
            }
        }
        return true;
    }
};

1109. 航班预订统计

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

请你返回一个长度为 n 的数组 answer，其中 answer[i] 是航班 i 上预订的座位总数。

示例 1：

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]

示例 2：

输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号        1   2
预订记录 1 ：   10  10
预订记录 2 ：       15
总座位数：      10  25
因此，answer = [10,25]

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        //vector<int> result;
        int size = bookings.size();
        vector<int> vector1;
        vector<int> result(n+1,0);

        for (int i = 0; i < size; i++) {
            result[bookings[i][0] - 1] += bookings[i][2];
            result[bookings[i][1]] -= bookings[i][2];
        }

        for (int i = 1; i < n; ++i) {
            result[i] += result[i - 1];
        }

        result.pop_back();

        return result;

    }
};

这篇关于编程-差分数组的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！