接外包,有相关需求的可以联系我:Telegram | Email

1109. 航班预订统计 | 差分数组

该文章创建(更新)于02/17/2022,请注意文章的时效性!

描述

这里有 n 个航班,它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ,表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti (包含 firsti 和 lasti )的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer,里面的元素是每个航班预定的座位总数。

思路

差分数组,注意差分数组的变化的临界值判断。

CODE

  • Time Limit Exceeded
class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        # 结果初始化
        result = []
        for i in range(n):
            result.append(0)


        for m in range(bookings.__len__()):
            diff = self.diffList(result,bookings[m][0],bookings[m][1],bookings[m][2])

            result[0] = diff[0]
            for n in range(len(result) - 1):
                result[n + 1] = result[n] + diff[n+1]

        return result

    # 差分数组更新方法
    # m 对应dif 的 m - 1
    def diffList(self,inputList,m,n,add):

        # 差分数组构造
        dif = [inputList[0]]
        for i in range(len(inputList) - 1):
            dif.append(inputList[i+1] - inputList[i])

        dif[m - 1] += add

        if n != len(inputList):
            dif[n] -= add

        return dif        
  • Accept

先创建所有改变结果的差分数组,最后再递推结果。再原基础上进行构造差分数组,优化了存储空间。

class Solution4:
    def corpFlightBookings(self, bookings, n):
        # 创造一个初始结果list
        f = [0 for _ in range(n)]
        print(f)

        for s, e, diff in bookings:
            print("s " + str(s) + "\te " + str(e) + "\tdiff " + str(diff))
            # 这里是为了我们常规理解的位置和list位置相对应
            s -= 1
            e -= 1

            # 差分数组只更改了区间端口的两个值
            # 先构造了完整的差分数组
            # 没有新建,在原值上进行了更新,优化了存储空间
            # 谁说了差分数组只能新建一个的?新建可能容易理解一些
            # 开始改变的端口
            f[s] += diff
            # 这里是为了避免改变有可能到最后一个也需要改变的情况
            if e + 1 < n:
                # 撤销改变
                f[e + 1] -= diff
            print(f)
            print("------------------------------------------")

        # 再用差分数组对结果值进行反推
        for i in range(1, n):
            print(i)
            print(f)
            f[i] += f[i - 1]
            print('-------------------')
        return f

S4 = Solution4()
booking = [[1,2,10],[2,3,20],[2,5,25],[5,5,15],[2,2,3]]
n = 5
result = str(S4.corpFlightBookings(booking,n))
print("##################################")
print(result)


👇 Share | 分享 👇


要不赞赏一下?

微信
支付宝
PayPal
Bitcoin

版权声明 | Copyright

除非特别说明,本博客所有作品均采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明转自-
https://www.emperinter.info/2022/02/17/corporate-flight-bookings/


要不聊聊?

我相信你准备留下的内容是经过思考的!【勾选防爬虫,未勾选无法留言】

*

*



微信公众号

👉 NewsLetter ❤️ 邮箱订阅 👈

优惠码