[leetcode 差分数组] 拼车 M

我会带着你远行 2024-02-05 12:49 15阅读 0赞

车上最初有 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  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### **CSJerry\_差分数组\_前缀和\_go** ####

*  思路

计算路程中每一段的人数
    再计算前缀和

var (
        people = 0
        from = 1
        to = 2
        maxLength = 1001
    )
    
    
    
    
    func carPooling(trips [][]int, capacity int) bool {
    // 建立差分数组
        diff := []int{}
        for i := 0; i < maxLength; i++ {
            diff = append(diff, 0)
        }
        for _, trip := range trips {
            diff[trip[from]] += trip[people]
            diff[trip[to]] -= trip[people]
        }
    
    
        // 计算前缀和
        var preSum int = 0
        for i := 0; i < maxLength; i++ {
            preSum += diff[i]
            if preSum > capacity {
                return false
            }
        }
        return true
    
    
    }

:::

发表评论取消回复

表情：

评论列表（有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读

相关差分数组

include<bits/stdc++.h> using namespace std; define ll long long const ...

雨点打透心脏的1/2处/ 2024年04月18日 09:43/ 0 赞/ 59 阅读

相关差分数组的使用

一、问题现在，输入一个数组 `nums`，然后又要求给区间 `nums[2..6]` 全部加 1，再给 `nums[3..9]` 全部减 3，再给 `nums[0..4

绝地灬酷狼/ 2024年04月01日 16:30/ 0 赞/ 61 阅读

相关 [leetcode 差分数组] 拼车 M

车上最初有 capacity 个空座位。车只能向一个方向行驶（也就是说，不允许掉头或改变方向）给定整数 capacity 和一个数组 trips , trip\[i\]

我会带着你远行/ 2024年02月05日 12:49/ 0 赞/ 16 阅读

相关【算法】差分数组

目录 1.概述 2.代码实现 3.应用 > 本文参考： > [LABULADONG 的算法网站][LABULADONG] 1.概述（1）

骑猪看日落/ 2023年10月07日 22:37/ 0 赞/ 44 阅读

相关差分数组：PIPI的区间操作Ⅰ

差分数组：PIPI的区间操作Ⅰ 文章目录差分数组：PIPI的区间操作Ⅰ 差分数组问题：思路

以你之姓@/ 2023年10月06日 22:03/ 0 赞/ 11 阅读

相关差分数组+Tallest Cow

差分数组的定义和用途 1.定义：对于已知有n个元素的数列d，建立记录它每一项和前一项差值的差分数组f,f\[1\]=d\[1\]-0=d\[1\]。可以得到f\[i\

红太狼/ 2023年07月08日 02:49/ 0 赞/ 17 阅读

相关差分数组

文章目录差分数组 1.问题背景 2.解决方案 3.差分构造 4.应用差分数组 1.问题背景

清疚/ 2022年12月25日 06:57/ 0 赞/ 203 阅读

相关 LeetCode-1094 拼车

题目链接：源自LeetCode第142场周赛 [https://leetcode-cn.com/contest/weekly-contest-142/problems/c

男娘i/ 2022年01月05日 07:47/ 0 赞/ 178 阅读

相关差分数组

先来看一道例题，给定一个长度为n(n≤107)的数列\{a1,a2,…,an\}，初始状态为0，m(m≤107)次操作，每次可以选择一个区间\[l,r\]，使下标在这个区间内的

小咪咪/ 2021年12月24日 15:23/ 0 赞/ 216 阅读

相关数据结构之差分数组

2019-06-25 推荐博客阅读：[https://www.sohu.com/a/271430685\_100201031][https_www.sohu.com_a_27

太过爱你忘了你带给我的痛/ 2021年12月15日 04:09/ 0 赞/ 224 阅读