前缀和 LeetCode1094 拼车

本文主要是介绍前缀和 LeetCode1094 拼车，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1094. 拼车

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

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

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

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

当前人数是由当前上车人数-当前下车人数决定的。因为from和to小于1000，所以可以使用大小为1000的数组path，表示每个点上车和下车的人数之差。 默认为0.

遍历trips：t

path[t[1]]+=t[0]；path[t[2]]-=t[0];

然后对path求前缀和，如果前缀和大于最大容量，说明超载返回false.

最后返回true。

class Solution {
public:bool carPooling(vector<vector<int>>& trips, int capacity) {int path[1001];memset(path,0,sizeof(path));for(int i=0;i<trips.size();i++){vector<int>t=trips[i];path[t[1]]+=t[0];if(path[t[1]]>capacity)return false;path[t[2]]-=t[0];}int s=0;for(int i=0;i<1001;i++){s+=path[i];if(s>capacity)return false;}return true;}
};

这篇关于前缀和 LeetCode1094 拼车的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---