[leetcode] 1109. Corporate Flight Bookings

[leetcode] 1109. Corporate Flight bookings

Description

There are n flights, and they are labeled from 1 to n.

We have a list of flight bookings. The i-th booking bookings[i] = [i, j, k] means that we booked k seats from flights labeled i to j inclusive.

Return an array answer of length n, representing the number of seats booked on each flight in order of their label.

Example 1:

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5Output: [10,55,45,25,25]

Constraints:

1 <= bookings.length <= 20000.1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000.1 <= bookings[i][2] <= 10000

分析

题目的意思是：给定一个bookings的数组，数组中每个元素包含三个值，i,j,k，表示从第i到第j包含k个座位，现在按照顺序输出每个位置的座位数目。这道题我一开始用了暴力破解，果然超时了，最后参考了一下别人的代码，发现用一个求和数组就可以，我不太明白第一个循环是什么意思，但是我验证过了，却是最后求和得到的是正确的结果，对于例1，这里我把第一个循环得到的res输出输出来：

[10,20+25,-10,-20,0,-25]

然后按照第二个循环求和就能得到答案，我晕了。

代码

class Solution: def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]: res=[0]*(n+1) for i,j,k in bookings: res[i-1]+=k res[j]-=k res.pop() for i in range(1,n): res[i]+=res[i-1] return res

参考文献

​​[LeetCode] Python O(n) solution | Top 98% Speed | 9 Lines of Code​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。