โปรแกรมค้นหาจำนวนบัสขั้นต่ำจะต้องผ่านจุดหยุดทั้งหมดใน Python

สมมติว่าเรามีรายการหมายเลขที่เรียกว่า nums ซึ่งแสดงป้ายรถเมล์ในสายที่ nums[i] แสดงเวลาที่รถบัสต้องมาถึงสถานี i ตอนนี้รถเมล์ทำได้แค่วิ่งไปข้างหน้า เราต้องหาจำนวนรถเมล์ขั้นต่ำที่จำเป็นในการผ่านป้ายทั้งหมด

ดังนั้น หากอินพุตเท่ากับ nums =[1, 2, 7, 9, 3, 4] เอาต์พุตจะเป็น 2 เนื่องจากบัสหนึ่งบัสสามารถหยุดได้ [1, 2, 3, 4] และอีกบัสหนึ่งทำได้ [ 7, 9].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้-

• ตอบ :=0

• เห็น :=รายการที่มีความยาวเท่ากับ nums และเริ่มต้นเป็นเท็จ

• สำหรับแต่ละดัชนี i และ n ที่สอดคล้องกันใน nums ทำ

  • ถ้าเห็น[i] เป็นเท็จ แล้ว

    • เห็น[i] :=จริง

    • ans :=ans + 1

    • ก่อนหน้า :=n

    • สำหรับ j ในช่วง i+1 ถึงขนาดของ nums ให้ทำ

      • ถ้า nums[j]> ก่อนหน้า และ เห็น[j] เป็นเท็จ แล้ว

        • เห็น[j] :=จริง

        • ก่อนหน้า :=nums[j]

• กลับมาอีกครั้ง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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