สมมติว่าเราต้องการเขียนคลาสที่เรียกว่า RecentCounter เพื่อนับคำขอล่าสุด คลาสนี้มีเมธอดเดียวเท่านั้น:ping(t) โดยที่ t แทนเวลาในหน่วยมิลลิวินาที การดำเนินการนี้จะส่งคืนจำนวน ping ที่เกิดขึ้นตั้งแต่ 3000 มิลลิวินาทีที่แล้วจนถึงปัจจุบัน ค่า ping ที่มีเวลาใน [t - 3000, t] จะนับรวมค่า ping ปัจจุบันด้วย และรับประกันได้ว่าการเติมเงินทุกครั้งจะใช้ค่า t ที่มากกว่าเดิมอย่างเคร่งครัด
ดังนั้น หากอินพุตเป็นเหมือน Call ping สี่ครั้ง ping(1), ping(100), ping(3001), ping(3002) ผลลัพธ์จะเป็น 1,2,3,3 ตามลำดับ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- เริ่มต้นคลาสโดยสร้างหนึ่งคิว เริ่มแรกจะว่างเปล่า
- กำหนดฟังก์ชัน ping() นี่จะใช้เวลา t
- ในขณะที่ขนาดของคิวไม่ใช่ 0 และ t -que[0]> 3000 ทำ
- ลบองค์ประกอบแรกออกจากคิว
- ใส่ t ที่ท้ายคิว
- ขนาดส่งคืนของคิว
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class RecentCounter: def __init__(self): self.queue = [] def ping(self, t): while len(self.queue) and t - self.queue[0] > 3000: self.queue.pop(0) self.queue.append(t) return len(self.queue) ob = RecentCounter() print(ob.ping(1)) print(ob.ping(100)) print(ob.ping(3001)) print(ob.ping(3002))
อินพุต
ob.ping(1) ob.ping(100) ob.ping(3001) ob.ping(3002)
ผลลัพธ์
1 2 3 3
