【Leetcode Daily】1109航班预订统计

发表于2025-12-06|更新于2025-12-06|力扣日常 | LeetcodeDaily

|总字数:208|阅读时长:1分钟|浏览量:

题目浅析

想查看原题可以点击题目链接。
简单地说，就是给一个航班预定表，内容分别是起始航班下标，终止航班下标，预订座位数组成的多个数据，求最终每个航班预定的座位数。

思路分享

越是做差分的题，越是发现，差分十分擅长处理增减的累计。拿此题来讲，只要通过差分记录各个航班的累计座位数，然后求前缀和即可。

https://leetcode.cn/problems/corporate-flight-bookings/solutions/968214/hang-ban-yu-ding-tong-ji-by-leetcode-sol-5pv8/

代码解答（强烈建议自行解答后再看）

参考题解

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        rec = [0]*(n+2)
        for start, last, seats in bookings:
            rec[start] += seats
            rec[last+1] -= seats
        return list(accumulate(rec[1:n+1]))

文章作者: 陆爻齐-LuYaoQi

文章链接: http://hslix.github.io/posts/9c996188.html

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！

Algorithm 前缀和差分

相关推荐

【Leetcode Daily】1094拼车

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个二维数组，其中的元素为长度 3 的一维数组，三个值分别是上车的人数，上车的下标，下车的下标，求整个过程中，车上的人数是否都小于 capacity。思路分享此前对于一段值的差值用前缀和处理，而前缀和的反面则是差分，求两个值的差值。所以差分记录的是值的变化，一个特点是，对于 a-b 区间的值加 10，相当于在差分数组上的 a 处加 10，b 处减 10. https://leetcode.cn/problems/car-pooling/solutions/2550264/suan-fa-xiao-ke-tang-chai-fen-shu-zu-fu-9d4ra/ 所以本题只要先求出整个数组的差分，再对差分做前缀和，过程中判断是否有值超过阈值即可。代码解答（强烈建议自行解答后再看）参考题解 12345678class Solution: def carPooling(self, trips: List[List[int]], capacity: int) -> bool: ...

【Leetcode Daily】2848与车相交的点

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个二维数组，内部的一维数组代表汽车的长度占坐标的起始与终点，汽车之间可重合，求所有汽车共占多少点。思路分享通过一维差分记录每个车占的地方，然后求前缀和，一旦值大于等于 1，说明至少有一辆或多辆车占据，可记 1. https://leetcode.cn/problems/points-that-intersect-with-cars/solutions/2435384/chai-fen-shu-zu-xian-xing-zuo-fa-by-endl-3xpm/ 代码解答（强烈建议自行解答后再看）参考题解 1234567class Solution: def numberOfPoints(self, nums: List[List[int]]) -> int: rec = [0]*101 for start, end in nums: rec[start-1] += 1 rec[end] -= 1 ...

【Leetcode Daily】1893检查是否区域内所有整数都被覆盖

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个二维数组，其中的元素是长度为 2 的一维数组，代表覆盖的区间，题目会再给一个区间，问整个区间是不是都被覆盖了。思路分享简单的一维差分就可以了，这里就细化一点陆爻齐做了几天差分的感受，前缀和更多用于子数组之间的差，而差分则往往用于将一段段连续的变化转换成离散的形式，然后再组合成整体的变化。 https://leetcode.cn/problems/check-if-all-the-integers-in-a-range-are-covered/solutions/825466/jian-cha-shi-fou-qu-yu-nei-suo-you-zheng-5hib/ 代码解答（强烈建议自行解答后再看）参考题解 12345678class Solution: def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool: rec = [0] * 52 for start,...

【Leetcode Daily】1854人口最多的年份

题目浅析想查看原题可以点击题目链接。简单地说，就是给二维数组，其中的元素代表一个人的出生和死亡年份，计算人口最多的年份（同样多的取早）思路分享由于死亡年份不计入人口，所以不需要通过在末尾加一。其余的内容只是简单的一维差分，不再赘述。 https://leetcode.cn/problems/maximum-population-year/solutions/766081/ren-kou-zui-duo-de-nian-fen-by-leetcode-5m7r4/ 代码解答（强烈建议自行解答后再看）参考题解 1234567891011121314151617class Solution: def maximumPopulation(self, logs: List[List[int]]) -> int: rec = [0]*101 base_year = 1950 for birth, death in logs: rec[birth-base_year] += 1 ...

【Leetcode Daily】2960统计已测试设备

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个一维数组，从左向右遍历操作，若当前的数字大于零，则对其之后的所有数字做减一操作，这算一次操作，求总共的操作数。思路分享暴力模拟的思想是每次遍历到一个大于零的数字，就向后遍历减一。但是学了差分的思想后，完全可以在差分数组在对应下标做减一，但是差分数组还可以简化，直接用一个变量记录当前的操作数，也就是后面的数字需要减的数字，若当前数字大于操作数，才算操作。 https://leetcode.cn/problems/count-tested-devices-after-test-operations/solutions/2560949/on-zuo-fa-pythonjavacgo-by-endlesscheng-fc5k/ 代码解答（强烈建议自行解答后再看）参考题解 123456789class Solution: def countTestedDevices(self, batteryPercentages: List[int]) -> int: ans = 0 ...

【Leetcode Daily】3355零数组变换I

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个整数一维数组，和一个个区间，你可以从区间中选任意多个下标做减一操作，求操作完后，最终数组是否全为零。思路分享本质上还是求差分的前缀和，任选下标的本质，是如果差分对应的值大于数组也没关系，毕竟可以选择不要，所以只要关注减不干净的就行。 https://leetcode.cn/problems/zero-array-transformation-i/solutions/2991455/mo-ban-chai-fen-shu-zu-pythonjavacgo-by-i4axs/ 代码解答（强烈建议自行解答后再看）参考题解 123456789101112class Solution: def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool: n = len(nums) rec = [0]*(n+1) for l, r in queries: ...

数据加载中