Giả sử chúng ta muốn viết một lớp có tên là RecentCounter để đếm các yêu cầu gần đây. Lớp này chỉ có một phương thức:ping (t), trong đó t đại diện cho một số thời gian tính bằng mili giây. Điều này sẽ trả về số ping đã được thực hiện từ 3000 mili giây trước cho đến nay. Bất kỳ ping nào có thời gian tính bằng [t - 3000, t] sẽ được tính, bao gồm cả ping hiện tại. Và nó được đảm bảo rằng mọi cuộc gọi nạp tiền sử dụng một giá trị t lớn hơn trước.
Vì vậy, nếu đầu vào giống như Gọi ping bốn lần ping (1), ping (100), ping (3001), ping (3002), thì đầu ra sẽ lần lượt là 1,2,3,3.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Khởi tạo lớp bằng cách tạo một hàng đợi, ban đầu lớp này trống
- Xác định một hàm ping (). Điều này sẽ mất t
- trong khi kích thước của hàng đợi không phải là 0 và t - hàng đợi [0]> 3000, hãy thực hiện
- xóa phần tử đầu tiên khỏi hàng đợi
- chèn t vào cuối hàng đợi
- trả về kích thước của hàng đợi
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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))
Đầu vào
ob.ping(1) ob.ping(100) ob.ping(3001) ob.ping(3002)
Đầu ra
1 2 3 3