Java教程

编程-差分数组

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

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

给你一个二维整数数组 ranges 和两个整数 left 和 right 。每个 ranges[i] = [starti, endi] 表示一个从 starti 到 endi 的 闭区间 。

如果闭区间 [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. 拼车

假设你是一位顺风车司机,车上最初有 capacity 个空座位可以用来载客。由于道路的限制,车 只能 向一个方向行驶(也就是说,不允许掉头或改变方向,你可以将其想象为一个向量)。

这儿有一份乘客行程计划表 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. 航班预订统计

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

有一份航班预订表 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;

    }
};

 


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