侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【哈希表, 差分数组】拼车

GabrielxD
2022-06-04 / 0 评论 / 0 点赞 / 37 阅读 / 589 字 / 正在检测是否收录...

题目

1094. 拼车


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

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

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

示例 1:

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

示例 2:

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

提示:

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

解题

方法一:哈希表

思路

使用差分数组,原数组的最大长度是 10001000,且差分的区间是 [trips[i][1],trips[i][2]1][trips[i][1], trips[i][2] - 1],变化量是 trips[i][0]trips[i][0]
实际上只用统计 nums[1max(trips[i][1])]nums[1 \dots max(trips[i][1])] 之间的区间端点是否有超过 capacitycapacity 的值即可。

维护一个有序树集,键是时间点,值是对应的乘客变化量,并且按照时间升序排序。
然后遍历该集合,把每个时间点的乘客量算出来,如果乘客量超过了容量就返回 false,一直都没超过则返回 true

代码

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int n = trips.length;
        Map<Integer, Integer> map = new TreeMap<>();
        for (int[] trip : trips) {
            map.put(trip[1], map.getOrDefault(trip[1], 0) + trip[0]);
            map.put(trip[2], map.getOrDefault(trip[2], 0) - trip[0]);
        }
        int pas = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            pas += entry.getValue();
            if (pas > capacity) return false;
        }
        return true;
    }
}
优化

数据范围比较小(0<=fromi<toi<=10000 <= from_i < to_i <= 1000)所以可以开一个大小为 1001 的数组代替集合。

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] diffs = new int[1001];
        for (int[] trip : trips) {
            diffs[trip[1]] += trip[0];
            diffs[trip[2]] -= trip[0];
        }
        int pas = 0;
        for (int diff : diffs) {
            if ((pas += diff) > capacity) return false;
        }
        return true;
    }
}
0

评论区