leetcode做题笔记1094. 拼车

本文主要是介绍leetcode做题笔记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

思路一：差分数组

c++解法

class Solution {
public:bool carPooling(vector<vector<int>> &trips, int capacity) {int d[1001]{};for (auto &t : trips) {int num = t[0], from = t[1], to = t[2];d[from] += num;d[to] -= num;}int s = 0;for (int v : d) {s += v;if (s > capacity) {return false;}}return true;}
};

分析：

对本题可使用差分数组的方法解决，将每次遍历到下一个的时候判断车上人数是否超过限额，超过则输出false，反之到最后还是没有超过capacity则输出true

总结：

本题考察对数组的应用，利用差分数组将路径上的人数用数组记录下来，在路程中判断人数是否会超过容量即可解决

这篇关于leetcode做题笔记1094. 拼车的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---