1094. 拼车

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

题目描述

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

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

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 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

解题思路

这是一道比较简单差分数组的应用题：

1. 初始化一个长度为 1005 的数组 arr，用于存储每个时间点的乘客数量。数组的索引代表时间点，数组的值代表该时间点的乘客数量。数组使用 fill(0) 初始化，意味着所有时间点的初始乘客数量为 0。

2. 遍历 trips 数组中的每个行程 trip。对于每个行程，执行以下操作：

   • 在出发时间 trip[1] 上增加乘客数量 trip[0]（即上车人数）。
   • 在到达时间 trip[2] 上减少乘客数量 trip[0]（即下车人数）。

3. 遍历数组 arr，累加每个时间点的乘客数量。这样做的目的是为了计算每个时间点的总乘客数量，考虑到之前的乘客可能在更早的时间点上车或下车。

4. 在累加过程中，检查任何时间点的总乘客数量是否超过了车辆的容量 capacity。如果是，返回 false，表示在某个时间点，车上的乘客数量超过了车辆的容量。

5. 如果遍历完整个数组后没有发现超过容量的情况，返回 true，表示车辆可以容纳所有行程的乘客。

AC代码

/*** @param {number[][]} trips* @param {number} capacity* @return {boolean}*/
var carPooling = function (trips, capacity) {const arr = new Array(1005).fill(0);trips.forEach((trip) => {arr[trip[1]] += trip[0];arr[trip[2]] -= trip[0];});for (let i = 0; i < arr.length; i++) {arr[i] += arr[i - 1] || 0;if (arr[i] > capacity) return false;}return true;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。