What is the main pattern used in Implement Router problem?

The key pattern is array scanning combined with hash lookup, allowing efficient packet ordering and duplicate detection.

How do I handle memory limits when adding packets?

Use a deque to store packets and a hash map for lookups; reject new packets if memory is full, maintaining consistent memory tracking.

Can getCount be optimized instead of scanning all packets?

Yes, keep packets sorted by timestamp and use binary search to find the range, which avoids scanning the entire array.

Why is deque preferred over array for packet storage?

Deque allows O(1) insertion at the back and removal from the front, matching FIFO forwarding without shifting elements.

What common mistakes occur in Implement Router?

Forgetting to update the hash map on forwarding, scanning linearly for counts, or exceeding memory limits are frequent errors.

#3508

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

设计路由器

请你设计一个数据结构来高效管理网络路由器中的数据包。每个数据包包含以下属性： source ：生成该数据包的机器的唯一标识符。 destination ：目标机器的唯一标识符。 timestamp ：该数据包到达路由器的时间戳。实现 Router 类： Router(int memoryLimit…

数组哈希表二分查找设计队列

题目描述

请你设计一个数据结构来高效管理网络路由器中的数据包。每个数据包包含以下属性：

source：生成该数据包的机器的唯一标识符。
destination：目标机器的唯一标识符。
timestamp：该数据包到达路由器的时间戳。

实现 Router 类：

Router(int memoryLimit)：初始化路由器对象，并设置固定的内存限制。

memoryLimit 是路由器在任意时间点可以存储的最大数据包数量。
如果添加一个新数据包会超过这个限制，则必须移除 最旧的 数据包以腾出空间。

bool addPacket(int source, int destination, int timestamp)：将具有给定属性的数据包添加到路由器。

如果路由器中已经存在一个具有相同 source、destination 和 timestamp 的数据包，则视为重复数据包。
如果数据包成功添加（即不是重复数据包），返回 true；否则返回 false。

int[] forwardPacket()：以 FIFO（先进先出）顺序转发下一个数据包。

从存储中移除该数据包。
以数组 [source, destination, timestamp] 的形式返回该数据包。
如果没有数据包可以转发，则返回空数组。

int getCount(int destination, int startTime, int endTime)：

返回当前存储在路由器中（即尚未转发）的，且目标地址为指定 destination 且时间戳在范围 [startTime, endTime]（包括两端）内的数据包数量。

注意：对于 addPacket 的查询会按照 timestamp 的非递减顺序进行。

示例 1：

输入：
["Router", "addPacket", "addPacket", "addPacket", "addPacket", "addPacket", "forwardPacket", "addPacket", "getCount"]
[[3], [1, 4, 90], [2, 5, 90], [1, 4, 90], [3, 5, 95], [4, 5, 105], [], [5, 2, 110], [5, 100, 110]]

输出：
[null, true, true, false, true, true, [2, 5, 90], true, 1]

解释：

Router router = new Router(3); // 初始化路由器，内存限制为 3。
router.addPacket(1, 4, 90); // 数据包被添加，返回 True。
router.addPacket(2, 5, 90); // 数据包被添加，返回 True。
router.addPacket(1, 4, 90); // 这是一个重复数据包，返回 False。
router.addPacket(3, 5, 95); // 数据包被添加，返回 True。
router.addPacket(4, 5, 105); // 数据包被添加，[1, 4, 90] 被移除，因为数据包数量超过限制，返回 True。
router.forwardPacket(); // 转发数据包 [2, 5, 90] 并将其从路由器中移除。
router.addPacket(5, 2, 110); // 数据包被添加，返回 True。
router.getCount(5, 100, 110); // 唯一目标地址为 5 且时间在 [100, 110] 范围内的数据包是 [4, 5, 105]，返回 1。

示例 2：

输入：
["Router", "addPacket", "forwardPacket", "forwardPacket"]
[[2], [7, 4, 90], [], []]

输出：
[null, true, [7, 4, 90], []]

解释：

Router router = new Router(2); // 初始化路由器，内存限制为 2。
router.addPacket(7, 4, 90); // 返回 True。
router.forwardPacket(); // 返回 [7, 4, 90]。
router.forwardPacket(); // 没有数据包可以转发，返回 []。

提示：

2 <= memoryLimit <= 10⁵
1 <= source, destination <= 2 * 10⁵
1 <= timestamp <= 10⁹
1 <= startTime <= endTime <= 10⁹
addPacket、forwardPacket 和 getCount 方法的总调用次数最多为 10⁵。
对于 addPacket 的查询，timestamp 按非递减顺序给出。

lightbulb

解题思路

方法一：哈希表 + 队列 + 二分查找

我们用一个哈希表 $\textit{vis}$ 来存储已经添加过的数据包的哈希值，用一个队列 $\textit{q}$ 来存储当前路由器中的数据包，用一个哈希表 $\textit{idx}$ 来记录每个目标地址已经转发的数据包数量，用一个哈希表 $\textit{d}$ 来存储每个目标地址对应的时间戳列表。

对于 $\textit{addPacket}$ 方法，我们计算数据包的哈希值，如果已经存在于 $\textit{vis}$ 中，则返回 $\text{false}$ ；否则将其添加到 $\textit{vis}$ 中，并检查当前队列的大小是否超过内存限制，如果超过则调用 $\textit{forwardPacket}$ 方法移除最旧的数据包，然后将新数据包添加到队列中，并将时间戳添加到对应目标地址的时间戳列表中，最后返回 $\text{true}$ 。时间复杂度为 $O(1)$ 。

对于 $\textit{forwardPacket}$ 方法，如果队列为空则返回空数组；否则移除队列头部的数据包，并从 $\textit{vis}$ 中删除其哈希值，更新对应目标地址的已转发数据包数量，最后返回该数据包。时间复杂度为 $O(1)$ 。

对于 $\textit{getCount}$ 方法，我们获取对应目标地址的时间戳列表和已转发数据包数量，然后使用二分查找找到时间戳在指定范围内的数量，最后返回该数量。时间复杂度为 $O(\log n)$ ，其中 $n$ 是时间戳列表的长度。

空间复杂度 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

class Router:

    def __init__(self, memoryLimit: int):
        self.lim = memoryLimit
        self.vis = set()
        self.q = deque()
        self.idx = defaultdict(int)
        self.d = defaultdict(list)

    def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
        x = self.f(source, destination, timestamp)
        if x in self.vis:
            return False
        self.vis.add(x)
        if len(self.q) >= self.lim:
            self.forwardPacket()
        self.q.append((source, destination, timestamp))
        self.d[destination].append(timestamp)
        return True

    def forwardPacket(self) -> List[int]:
        if not self.q:
            return []
        s, d, t = self.q.popleft()
        self.vis.remove(self.f(s, d, t))
        self.idx[d] += 1
        return [s, d, t]

    def f(self, a: int, b: int, c: int) -> int:
        return a << 46 | b << 29 | c

    def getCount(self, destination: int, startTime: int, endTime: int) -> int:
        ls = self.d[destination]
        k = self.idx[destination]
        i = bisect_left(ls, startTime, k)
        j = bisect_left(ls, endTime + 1, k)
        return j - i


# Your Router object will be instantiated and called as such:
# obj = Router(memoryLimit)
# param_1 = obj.addPacket(source,destination,timestamp)
# param_2 = obj.forwardPacket()
# param_3 = obj.getCount(destination,startTime,endTime)

speed

复杂度分析

指标	值
时间	complexity: addPacket and forwardPacket are O(1) amortized due to deque and hash map usage; getCount is O(log n) for binary search over timestamps. Space complexity: O(n) for storing packets in deque and hash map.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask about handling memory limits when adding duplicate packets.
question_mark
Check if forwarding maintains correct packet order under constraints.
question_mark
Probe for efficient counting of packets within timestamp ranges.

warning

常见陷阱

外企场景

error
Not removing packets from the hash map when forwarding, causing false duplicates.
error
Scanning the entire array for counts instead of using binary search.
error
Failing to respect memory limits, leading to incorrect addPacket results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Router with priority-based packet forwarding instead of FIFO order.
arrow_right_alt
Router supporting dynamic memory resizing with the same addPacket logic.
arrow_right_alt
Router allowing bulk forwarding of multiple packets in one operation.

help

常见问题

外企场景

继续练习

#2713 矩阵中严格递增的单元格数 #3507 移除最小数对使数组有序 I #3510 移除最小数对使数组有序 II

设计路由器

题目描述

解题思路

方法一： 哈希表 + 队列 + 二分查找

复杂度分析

面试官常问的追问

常见陷阱

进阶变体

常见问题

What is the main pattern used in Implement Router problem?

How do I handle memory limits when adding packets?

Can getCount be optimized instead of scanning all packets?

Why is deque preferred over array for packet storage?

What common mistakes occur in Implement Router?

方法一：哈希表 + 队列 + 二分查找