厦门微网站建设,17zwd一起做网站官网,黄页网站软件下载免费app,下载浏览器车上最初有 capacity 个空座位。车 只能 向一个方向行驶#xff08;也就是说#xff0c;不允许掉头或改变方向#xff09;给定整数 capacity 和一个数组 trips , trip[i] [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客#xff0c;接他们和放他们的…车上最初有 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 1000trips[i].length 31 numPassengersi 1000 fromi toi 10001 capacity 1051094. 拼车 - 力扣Leetcode思路小而美的算法技巧差分数组 :: labuladong的算法小抄本题也是可以利用 差分数组来求解cclass Solution {
public:vectorint diff;void increment(vectorint diff, int i, int j, int val){diff[i] val;if(j diff.size()) {diff[j] - val;}}bool carPooling(vectorvectorint trips, int capacity) {diff vectorint(1001, 0);vectorint result(1001, 0);int maxLen 0;for(auto trip:trips) {int numPassengers trip[0];int from trip[1];int to trip[2];maxLen max(maxLen, to);increment(diff, from, to, numPassengers);}result[0] diff[0];for(int i1; imaxLen; i) {result[i] result[i-1] diff[i];}bool flag true;for(int i0; imaxLen; i) {if(result[i] capacity) {flag false;}}return flag;}
};
