• Leetcode 3508. Implement Router
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：3508. Implement Router

1. 解題思路

這一題就是按照題意寫作一下對應的函數即可。

我們需要注意的是，這里，定義的類當中需要包含以下一些內容：

1. 一個所有item的集合，來快速判斷當前給到的包是否已經出現過了；
2. 一個按照時間戳以及輸入順序有序排列的所有package的隊列，從而確保可以彈出最早的包；
3. 一個按照destination進行分塊，且各自按照timestamp進行有序排列的序列，從而使得可以對getCount函數進行快速實現。

2. 代碼實現

給出python代碼實現如下：

class Router:def __init__(self, memoryLimit: int):self.idx = 0self.memoryLimit = memoryLimitself.seen = set()self.packets = []self.groups = defaultdict(list)def addPacket(self, source: int, destination: int, timestamp: int) -> bool:if (source, destination, timestamp) in self.seen:return Falseif len(self.packets) == self.memoryLimit:self.forwardPacket()self.seen.add((source, destination, timestamp))bisect.insort(self.packets, (timestamp, self.idx, source, destination))bisect.insort(self.groups[destination], (timestamp, self.idx))self.idx += 1return Truedef forwardPacket(self) -> List[int]:if len(self.packets) == 0:return []timestamp, idx, source, destination = self.packets.pop(0)self.seen.remove((source, destination, timestamp))self.groups[destination].pop(bisect.bisect_left(self.groups[destination], (timestamp, idx)))return [source, destination, timestamp]def getCount(self, destination: int, startTime: int, endTime: int) -> int:left = bisect.bisect_left(self.groups[destination], (startTime, -1))right = bisect.bisect_left(self.groups[destination], (endTime+1, -1))return right-left

提交代碼評測得到：耗時544ms，占用內存101.5MB。