电子政务门户网站建设汇报,怎么用eclipse做网页,wordpress 风 轩,触动网站建设拼车问题#xff08;LeetCode 1094#xff09;的解析与C实现 Problem: 1094. 拼车 题目背景
在本题中#xff0c;我们需要处理一个拼车的问题。假设一辆车有固定的座位容量#xff0c;我们需要根据乘客的上车和下车地点#xff0c;判断车辆是否能够在整个行程中满足不超过…拼车问题LeetCode 1094的解析与C实现 Problem: 1094. 拼车 题目背景
在本题中我们需要处理一个拼车的问题。假设一辆车有固定的座位容量我们需要根据乘客的上车和下车地点判断车辆是否能够在整个行程中满足不超过最大容量的要求。
题目描述
给定一个整数 capacity 表示车的座位数和一个数组 trips。trips[i] 表示第 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 10^5
解题思路
为解决这个问题我们可以使用树状数组Fenwick Tree来处理区间的增加操作。对于每次旅行我们将乘客数量加到上车点并在下车点之后减去相同的乘客数。然后我们检查每个点的乘客总数是否超过车辆容量。
C 代码实现
#include vector
#include iostream
using namespace std;class Solution {
public:bool carPooling(vectorvectorint trips, int capacity) {vectorint tree(1002, 0);// 树状数组的lowbit返回x的二进制中的最右侧的1对应的数值auto lowbit [](int x) - int {return x -x;};// 对[idx, 1000]这个区间增加valauto add [](int idx, int val) {for (int i idx; i 1001; i lowbit(i)) {tree[i] val;}};// 查询[0, idx]的和auto query [](int idx) - int {int res 0;for (int i idx; i; i - lowbit(i)) {res tree[i];}return res;};for (auto t : trips) {int num t[0], from t[1], to t[2];add(from 1, num); // 给[from, 1000]加上numadd(to 1, -num); // 给[to, 1000]减去num}for (int i 0; i 1001; i) {if (query(i) capacity) {return false;}}return true;}
};测试用例
int main() {Solution solution;vectorvectorint trips1 {{2, 1, 5}, {3, 3, 7}};int capacity1 4;cout Test Case 1: (solution.carPooling(trips1, capacity1) ? True : False) endl;vectorvectorint trips2 {{2, 1, 5}, {3, 3, 7}};int capacity2 5;cout Test Case 2: (solution.carPooling(trips2, capacity2) ? True : False) endl;return 0;
}在这个C实现中我们利用树状数组的特性来优化区间更新和查询操作从而有效处理拼车问题的乘客统计。
