Chương trình tìm số lượng bus tối thiểu được yêu cầu để đi qua tất cả các điểm dừng bằng Python

Giả sử chúng ta có một danh sách các số gọi là nums và hiển thị các điểm dừng xe buýt trên một đường trong đó nums [i] hiển thị thời gian xe buýt phải đến trạm i. Bây giờ xe buýt chỉ có thể di chuyển về phía trước, chúng tôi phải tìm số lượng xe buýt tối thiểu cần thiết để đi qua tất cả các điểm dừng.

Vì vậy, nếu đầu vào là nums =[1, 2, 7, 9, 3, 4], thì đầu ra sẽ là 2, vì một xe buýt có thể dừng lại [1, 2, 3, 4] và một xe buýt khác có thể làm [ 7, 9].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau−

• ans:=0

• saw:=một danh sách có độ dài bằng nums và ban đầu được lấp đầy bằng false

• đối với mỗi chỉ số i và n tương ứng trong số, thực hiện

  • nếu thấy [i] là sai, thì

    • đã thấy [i]:=Đúng

    • ans:=ans + 1

    • trước:=n

    • đối với j trong phạm vi i + 1 đến kích thước của nums, thực hiện

      • nếu nums [j]> eval và saw [j] là false, thì

        • đã thấy [j]:=Đúng

        • trước:=nums [j]

• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

2