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

1094. 拼车 | 差分数组

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

Description

假设你是一位顺风车司机,车上最初有 capacity 个空座位可以用来载客。由于道路的限制,车 只能 向一个方向行驶(也就是说,不允许掉头或改变方向,你可以将其想象为一个向量)。

这儿有一份乘客行程计划表 trips[][],其中 trips[i] = [num_passengers, start_location, end_location] 包含了第 i 组乘客的行程信息:

  • 必须接送的乘客数量;
  • 乘客的上车地点;
  • 以及乘客的下车地点。

这些给出的地点位置是从你的 初始 出发位置向前行驶到这些地点所需的距离(它们一定在你的行驶方向上)。

请你根据给出的行程计划表和车子的座位数,来判断你的车是否可以顺利完成接送所有乘客的任务(当且仅当你可以在所有给定的行程中接送所有乘客时,返回 true,否则请返回 false)。

CODE

这里最重要的是理解上车地点

class Solution5:
    def carPooling(self, trips, capacity):
        tmp = [0 for _ in range(1000)]

        #构造差分数组
        for add,m,n in trips:
            # 对应list的值
            # m -= 1
            # n -= 1
            # 题中这里的m是可以为0的
            print('---------------------------------------')
            if m > 0:
                tmp[m] += add
            elif m == 0:
                tmp[0] = add

            if n < 1000:
                # tmp[n + 1] -= add
                # 这里为n的原因是,客户虽然是到第n站,
                # 但第n站先下车就不会占座
                tmp[n] -= add
            print(tmp)
            print('---------------------------')

        if(tmp[0] > capacity):
            return False

        # get结果
        for k in range(1,1000):
            tmp[k] += tmp[k - 1]
            if (tmp[k] > capacity):
                return  False
        print(tmp)
        return True

S5 = Solution5()
# trips = [[2,1,5],[3,3,7]]
trips = [[2,1,5],[3,5,7]]
# trips = [[9,0,1],[3,3,7]]
# capacity = 5
capacity = 3
print(S5.carPooling(trips,capacity))


👇 Share | 分享 👇


要不赞赏一下?

微信
支付宝
PayPal
Bitcoin

版权声明 | Copyright

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


要不聊聊?

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

*

*



微信公众号

👉 NewsLetter ❤️ 邮箱订阅 👈

优惠码