福田网站建设,wordpress knowall主题,做外贸网站平台有哪些内容,视频小广告是怎么制作的差分算法力扣1094题目描述学习代码思考力扣1094
题目描述
车上最初有 capacity 个空座位。车 只能 向一个方向行驶#xff08;也就是说#xff0c;不允许掉头或改变方向#xff09;
给定整数 capacity 和一个数组 trips , trip[i] [numPassengersi, fromi, toi] 表示第 …
差分算法力扣1094题目描述学习代码思考力扣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
提示
1 trips.length 1000 trips[i].length 3 1 numPassengersi 100 0 fromi toi 1000 1 capacity 105
来源力扣LeetCode 链接https://leetcode.cn/problems/car-pooling 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
学习
差分使用场景每个顺序节点上有增加或者减少
代码
去博客设置页面选择一款你喜欢的代码片高亮样式下面展示同样高亮的 代码片.
bool carPooling(int** trips, int tripsSize, int* tripsColSize, int capacity){// 构造出差分数组int* nums (int*)malloc(sizeof(int) * 1001);for(int i 0; i 1000; i) {nums[i] 0;}for (int i 0; i tripsSize; i) {nums[trips[i][1]] trips[i][0]; // 上车人数nums[trips[i][2]] - trips[i][0]; // 下车人数}// 实际容量数组int* caps (int*)malloc(sizeof(int) * 1001);for(int i 0; i 1001; i) {caps[i] 0;}caps[0] nums[0];if (caps[0] capacity) {return false;}for (int i 1; i 1001; i) {caps[i] nums[i] caps[i - 1];// 超出容量if (caps[i] capacity) {return false;}}return true;
}思考
易错点1数据大小不够导致溢出所以数组大小是1001 易错点2遗漏0站上车1站下车上车站人数超过容量场景 易错点3数组分配大小后要初始化为0
