โปรแกรมตรวจสอบลำดับป๊อปอัปที่กำหนดนั้นเหมาะสมหรือไม่ใน python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า pushes และรายการตัวเลขอื่นที่เรียกว่า pops เราต้องตรวจสอบว่านี่เป็นลำดับที่ถูกต้องของการดำเนินการ stack push และ pop หรือไม่

ดังนั้น ถ้าอินพุตเหมือน pushes =[1, 2, 5, 7, 9] pops =[2, 1, 9, 7, 5] ผลลัพธ์จะเป็น True ตามที่เราสามารถกด [1, 2] ก่อนแล้วจึงเปิดทั้งคู่ จากนั้นกด [5, 7, 9] แล้วเปิดทั้งหมด

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

• s :=สแต็คใหม่
• ผม :=0
• สำหรับแต่ละอิเลในการดัน ทำ
  • ดัน ele เป็น s
  • ในขณะที่ขนาดของ s> 0 และ pops[i] เป็นองค์ประกอบบนสุดของ s เหมือนกัน ให้ทำ
    • ลบองค์ประกอบด้านบนออกจาก s
    • ผม :=ผม + 1
• คืนค่า จริง เมื่อขนาดของ s เท่ากับ 0 มิฉะนั้น เท็จ

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

ตัวอย่าง

class Solution:
   def solve(self, pushes, pops):
      s = []
      i = 0

      for ele in pushes:
         s.append(ele)

         while len(s) > 0 and pops[i] == s[-1]:
            s.pop()
            i += 1

      return len(s) == 0

ob = Solution()
pushes = [1, 2, 5, 7, 9]
pops = [2, 1, 9, 7, 5]
print(ob.solve(pushes, pops))

อินพุต

[1, 2, 5, 7, 9], [2, 1, 9, 7, 5]

ผลลัพธ์

True