【LeetCode】每日一题 2023_12_2 拼车（模拟/差分）

文章目录

• 刷题前唠嗑
• 题目：拼车

刷题前唠嗑

LeetCode？启动！！！

题目：拼车

题目链接：1094. 拼车

题目描述

代码与解题思路

func carPooling(trips [][]int, capacity int) bool {
    var numPeople [1001]int
    for _, v := range trips {
        n, a, b := v[0], v[1], v[2]
        numPeople[a] += n
        numPeople[b] -= n
    }
    curCap := 0
    for _, v := range numPeople {
        curCap += v
        if curCap > capacity {
            return false
        }
    }
    return true
}

怎么说呢，今天的题目，我用的是模拟，代码流程如下

1. 枚举 trips 数组，然后在 a 位置上乘客，b 位置下乘客
2. 接着遍历记录乘客上下车的数组 numPeople，curCap 计数，如果超过了车的容量 capacity 就返回 false，否则返回 true

学习大佬题解

看了一圈，他们都说是什么差分的思想，然后我就顺便跑去入门了一下差分，学完了之后，在看这道题，emmm，感觉好像也没用上，总之我是看不出为什么说是差分的

差分的核心思想在于，创造差分数组之后（每个数 = 原数组中前一个数的差，计算他的前缀和就能得到原数组），只需要修改一个数，就能影响他及其他之后的区间的值