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

更新于：2020年10月5日

1K+ 次浏览

开启您的职业生涯

完成课程后获得认证

开始学习
广告