题目

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

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^5
1 <= source, destination <= 2 * 10^5
1 <= timestamp <= 10^9
1 <= startTime <= endTime <= 10^9
addPacket、forwardPacket 和 getCount 方法的总调用次数最多为 10^5。
对于 addPacket 的查询，timestamp 按递增顺序给出。

解题思路

1. 核心需求分析

我们来分解一下 Router 类需要高效完成的任务：

FIFO (先进先出) 管理: addPacket 添加最新的，forwardPacket 移除最旧的。这天然指向了**队列（Queue）**这种数据结构。
内存限制: 当队列满了之后，需要从队头（最旧的）移除一个元素。这同样符合队列的特性。
快速去重: addPacket 需要检查一个数据包 (source, destination, timestamp) 是否已经存在。对整个队列进行线性扫描太慢了（O(N)），我们需要一种近乎 O(1) 的查找方法。这自然会想到哈希集合（Hash Set）。
高效范围查询: getCount 需要快速统计特定 destination 在一个时间戳范围 [startTime, endTime] 内的数据包数量。如果遍历所有数据包，效率会很低（O(N)）。我们需要一种方法来：
- 首先按 destination 对数据包进行分组。
- 然后在每个分组内，对 timestamp 进行高效的范围查询。

2. 选择合适的数据结构

综合以上分析，我们不能用单一的数据结构来满足所有需求。我们需要组合使用多种数据结构，让它们各司其职。

collections.deque (双端队列): 这是实现 FIFO 队列的最佳选择。
- 作用: 作为我们主要的存储容器，维护数据包的进入和离开顺序。
- 优点: 在队列的两端（头部和尾部）添加和删除元素的时间复杂度都是 O(1)。这完美匹配了 addPacket (在尾部添加) 和 forwardPacket/内存溢出淘汰 (在头部删除) 的需求。
- 存储内容: 存储完整的数据包元组 (source, destination, timestamp)。
set (集合):
- 作用: 用于快速检测重复的数据包。
- 优点: 添加、删除和查找元素的平均时间复杂度都是 O(1)。
- 存储内容: 同样存储完整的数据包元组 (source, destination, timestamp)。
dict of lists (或 deques): 这是解决 getCount 效率问题的关键。
- 作用: 用于按 destination 对数据包的时间戳进行索引。
- 结构:
  - 键 (Key): destination (目标地址)。
  - 值 (Value): 一个有序的列表或双端队列，存储所有发往该 destination 的数据包的 timestamp。
- 为什么有序？: 题目有一个关键提示：“对于 addPacket 的查询会按照 timestamp 的递增顺序进行”。这意味着我们每次向这个列表（或 deque）追加时间戳时，它自然就是有序的。
- 如何查询？: 对于一个有序的列表，我们可以使用二分查找 (Binary Search) 来快速定位 startTime和 endTime 的边界，从而在 O(log K) 的时间内完成范围计数，其中 K 是发往该 destination 的数据包数量。这远比 O(N) 的线性扫描要快。

3. 各方法实现逻辑

现在我们把这些数据结构串联起来，看看每个方法具体如何工作。

__init__(self, memoryLimit)

初始化内存限制 self.memoryLimit。
初始化一个双端队列 self.packets_queue = deque() 用于 FIFO 存储。
初始化一个集合 self.packet_set = set() 用于去重。
初始化一个字典 self.dest_to_timestamps = defaultdict(list) (或 defaultdict(deque)) 用于 getCount查询。使用 defaultdict 可以简化代码，避免在插入新 destination 时检查键是否存在。

addPacket(source, destination, timestamp)

将输入参数组成一个元组 packet = (source, destination, timestamp)。
去重检查: 使用集合检查 if packet in self.packet_set:。如果是，直接返回 False。
内存限制检查:
- if len(self.packets_queue) == self.memoryLimit:，说明路由器已满。
- 从队列头部移除最旧的数据包: oldest_packet = self.packets_queue.popleft()。
- 同步更新另外两个数据结构：
  - 从集合中移除: self.packet_set.remove(oldest_packet)。
  - 从 dest_to_timestamps 字典中移除对应的时间戳。假设 old_dest = oldest_packet[1]，old_ts = oldest_packet[2]，我们需要从 self.dest_to_timestamps[old_dest] 这个列表中移除 old_ts。因为我们总是移除最旧的，所以它一定是列表中的第一个元素，执行 self.dest_to_timestamps[old_dest].pop(0) 即可。（如果用 deque，popleft() 效率更高）。
添加新数据包:
- 将新数据包添加到队列尾部: self.packets_queue.append(packet)。
- 添加到集合中: self.packet_set.add(packet)。
- 将时间戳添加到 dest_to_timestamps 字典中: self.dest_to_timestamps[destination].append(timestamp)。
返回 True。

时间复杂度: O(1)。所有操作（队列、集合、字典的添加/删除）都是常数时间复杂度。

forwardPacket()

检查队列是否为空: if not self.packets_queue:，返回空数组 []。
从队列头部取出并移除最旧的数据包: packet_to_forward = self.packets_queue.popleft()。
同步更新另外两个数据结构：
- 从集合中移除: self.packet_set.remove(packet_to_forward)。
- 从 dest_to_timestamps 字典中移除对应的时间戳（同上 addPacket 中的淘汰逻辑）。
将元组 packet_to_forward 转换为列表并返回。

时间复杂度: O(1)。

getCount(destination, startTime, endTime)

从 dest_to_timestamps 字典中获取该 destination 对应的时间戳列表: timestamps = self.dest_to_timestamps[destination]。
如果 destination 不存在或其时间戳列表为空，直接返回 0。
使用二分查找库（例如 Python 的 bisect 模块）来高效计数：
- 找到第一个大于等于 startTime 的位置 left_index = bisect_left(timestamps, startTime)。
- 找到第一个大于 endTime 的位置 right_index = bisect_right(timestamps, endTime)。
计数值就是这两个索引的差: count = right_index - left_index。
返回 count。

时间复杂度: O(log K)，其中 K 是发往该 destination 的数据包数量。

这个设计思路的核心是用空间换时间和为不同的操作选择最合适的数据结构。

操作	核心需求	解决方案	复杂度
`addPacket`, `forwardPacket`	FIFO 顺序和内存淘汰	`collections.deque`	O(1)
`addPacket`	快速去重	`set`	O(1)
`getCount`	按目标地址和时间范围高效查询	`dict` + 有序列表 + 二分查找	O(log K)

具体代码

class Router {
private:
    // 使用元组 (tuple) 来清晰地表示一个数据包
    // 格式: {source, destination, timestamp}
    using Packet = std::tuple<int, int, int>;

    int memoryLimit;

    // 1. FIFO 队列: 存储所有数据包，用于实现先进先出
    std::queue<Packet> packets_queue;
    
    // 2. 集合: 用于快速检测重复数据包 (O(logN) 查找)
    std::set<Packet> packet_set;
    
    // 3. 哈希表: 映射 destination -> timestamps 列表，用于高效 getCount
    // 值使用 deque 是为了 O(1) 时间复杂度的头部删除 (pop_front)
    std::unordered_map<int, std::deque<int>> dest_to_timestamps;

public:
    /**
     * @brief 构造函数，初始化路由器并设置内存限制
     */
    Router(int memoryLimit) {
        this->memoryLimit = memoryLimit;
    }
    
    /**
     * @brief 添加一个数据包
     * @return 如果成功添加（非重复），返回 true；否则返回 false
     */
    bool addPacket(int source, int destination, int timestamp) {
        Packet new_packet = std::make_tuple(source, destination, timestamp);
        
        // 步骤 1: 使用 set 检查数据包是否重复
        if (packet_set.count(new_packet)) {
            return false;
        }
        
        // 步骤 2: 检查内存是否已满。如果满了，则移除最旧的数据包
        if (packets_queue.size() == memoryLimit) {
            // 从 FIFO 队列的头部获取最旧的数据包
            Packet oldest_packet = packets_queue.front();
            packets_queue.pop();
            
            // 从另外两个数据结构中同步移除该旧数据包的信息
            packet_set.erase(oldest_packet);
            
            int old_dest = std::get<1>(oldest_packet);
            // 由于时间戳是递增的，要移除的时间戳一定是对应列表中的第一个
            dest_to_timestamps[old_dest].pop_front();
            
            // (可选优化) 如果某个 destination 已无数据包，从哈希表中移除该键
            if (dest_to_timestamps[old_dest].empty()) {
                dest_to_timestamps.erase(old_dest);
            }
        }
        
        // 步骤 3: 将新数据包添加到所有数据结构中
        packets_queue.push(new_packet);
        packet_set.insert(new_packet);
        dest_to_timestamps[destination].push_back(timestamp);
        
        return true;
    }
    
    /**
     * @brief 转发最旧的数据包
     * @return 返回被转发的数据包 [source, destination, timestamp]，如果没有则返回空数组
     */
    std::vector<int> forwardPacket() {
        // 检查路由器是否为空
        if (packets_queue.empty()) {
            return {}; // 返回空 vector
        }
        
        // 从队列头部获取并移除最旧的数据包
        Packet packet_to_forward = packets_queue.front();
        packets_queue.pop();
        
        // 从其他数据结构中同步移除
        packet_set.erase(packet_to_forward);
        
        int dest = std::get<1>(packet_to_forward);
        dest_to_timestamps[dest].pop_front();
        
        if (dest_to_timestamps[dest].empty()) {
            dest_to_timestamps.erase(dest);
        }
        
        // 将元组转换为 vector<int> 格式并返回
        return {std::get<0>(packet_to_forward), std::get<1>(packet_to_forward), std::get<2>(packet_to_forward)};
    }
    
    /**
     * @brief 统计指定 destination 和时间范围内的数据包数量
     * @return 返回数据包数量
     */
    int getCount(int destination, int startTime, int endTime) {
        // 如果哈希表中没有这个 destination 的记录，直接返回 0
        if (dest_to_timestamps.find(destination) == dest_to_timestamps.end()) {
            return 0;
        }
        
        // 获取该 destination 对应的时间戳列表 (一个有序的 deque)
        auto& timestamps = dest_to_timestamps.at(destination);
        
        // 使用二分查找来高效地定位范围
        // 1. 找到第一个 >= startTime 的元素
        auto it_start = std::lower_bound(timestamps.begin(), timestamps.end(), startTime);
        
        // 2. 找到第一个 > endTime 的元素
        auto it_end = std::upper_bound(timestamps.begin(), timestamps.end(), endTime);
        
        // 两个迭代器之间的距离就是符合条件的元素数量
        return std::distance(it_start, it_end);
    }
};

3508. 设计路由器

beautifulremi

题目

解题思路

1. 核心需求分析

2. 选择合适的数据结构

3. 各方法实现逻辑

具体代码