车上最初有 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
思路一:差分数组
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
总结:
本题考察对数组的应用,利用差分数组将路径上的人数用数组记录下来,在路程中判断人数是否会超过容量即可解决
原文地址:https://blog.csdn.net/si_mple_/article/details/134758889
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_31488.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。