Python 中的拼車問題

假設有一輛車，一開始有 capacity 個空座位供乘客使用。該車只向東行駛，所以我們不能掉頭向西行駛。我們給定了一個行程列表 trips，其中 trip[i] = [num_passengers, start_location, end_location]，包含有關第 i 次行程的資訊：num_passengers 是必須接送的乘客數量，以及接送他們的位置。此處的 location 是指從我們的車輛初始位置向東行駛的公里數。當且僅當接送所有乘客的所有已給定行程均可行時，我們的模組才會返回 True。因此，如果行程為 [[2,1,5],[3,3,7]]，容量為 5，則輸出將為 true。

為了解決這個問題，我們將按照以下步驟進行 −

  • 製作一個名為 stops 的陣列，大小為 1000，並用 0 填充
  • 對於行程中的 i
    • stops[i[1]] := stops[i[1]] + i[0]
    • stops[i[2]] := stops[i[1]] – i[0]
  • 對於 stops 中的 i −
    • capacity := capacity – i
    • 如果 capacity < 0，則返回 false
  • 當容量 >= 0 時返回真

讓我們參閱下列實現以加深理解 −

示例

 動態演示

class Solution(object):
   def carPooling(self, trips, capacity):
      stops = [0 for i in range(1001)]
      for i in trips:
         stops[i[1]]+=i[0]
         stops[i[2]]-=i[0]
      for i in stops:
         capacity-=i
         if capacity<0:
            return False
      return capacity>=0
ob = Solution()
print(ob.carPooling([[2,1,5],[3,3,7]],5))

輸入

[[2,1,5],[3,3,7]]
5

輸出

True

更新時間: 30-4 月-2020

666 檢視次數

開始你的 職業

透過完成課程獲得認證

開始
廣告