Python程式：查詢透過所有站點所需的最少公交車數量

假設我們有一個名為nums的數字列表，它表示一條線路上的公交車站，其中nums[i]表示公交車必須到達站點i的時間。由於公交車只能向前行駛，我們必須找到透過所有站點所需的最少公交車數量。

因此，如果輸入類似於nums = [1, 2, 7, 9, 3, 4]，則輸出將為2，因為一輛公交車可以停靠站點[1, 2, 3, 4]，而另一輛可以停靠站點[7, 9]。

為了解決這個問題，我們將遵循以下步驟：

• ans := 0

• seen := 一個列表，其長度與nums相同，最初填充為false

• 對於每個索引i和對應的n in nums，執行以下操作：

  • 如果seen[i]為false，則

    • seen[i] := True

    • ans := ans + 1

    • prev := n

    • 對於j in range i+1到nums的大小，執行以下操作：

      • 如果nums[j] > prev且seen[j]為false，則

        • seen[j] := True

        • prev := nums[j]

• 返回ans

讓我們來看下面的實現，以便更好地理解：

示例

線上演示

class Solution:
   def solve(self, nums):
   ans = 0
   seen = [False] * len(nums)
   for i, n in enumerate(nums):
      if not seen[i]:
         seen[i] = True
         ans += 1
         prev = n
   for j in range(i+1, len(nums)):
      if nums[j] > prev and not seen[j]: seen[j] = True
         prev = nums[j]
   return ans
ob = Solution()
nums = [1, 2, 7, 9, 3, 4]
print(ob.solve(nums))

輸入

[1, 2, 7, 9, 3, 4]

輸出

2

Arnab Chakraborty

更新於：2020年10月5日

1K+ 次瀏覽

開啟您的職業生涯

完成課程後獲得認證

開始學習