*359. Logger Rate Limiter
https://leetcode.com/problems/logger-rate-limiter/description/
solution
# hashmap 做一个类似 inverted index 功能
class Logger:
def __init__(self):
self.messageQueue = collections.deque()
self.messageSet = set()
def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
while self.messageQueue:
headTimestamp, headMessage = self.messageQueue[0]
if timestamp < headTimestamp + 10:
break
# 大于10秒的去掉
self.messageQueue.popleft()
self.messageSet.remove(headMessage)
if message in self.messageSet:
return False
self.messageQueue.append((timestamp, message))
self.messageSet.add(message)
return True
时间复杂度:O(n) 空间复杂度:O(n)
follow up
给定一个公共API,限制每个用户每秒只能调用1000次,如何实现?
counter
Token Bucket
Leak Bucket
https://zhuanlan.zhihu.com/p/20872901
Last updated