当前位置：首页 > 力扣 > 力扣3508题：队列+哈希表+时间戳索引解决路由器设计

力扣3508题：队列+哈希表+时间戳索引解决路由器设计

3个月前 (08-27)

一、题目解读

力扣3508题要求设计一个路由器类，支持添加数据包与转发操作。每个数据包包含源地址、目标地址和时间戳，需满足：

1. 内存容量限制，超出时需删除最早数据包；

2. 相同源-目标-时间戳的数据包仅允许添加一次；

3. 转发时返回最早待处理的数据包。题目核心在于平衡内存约束与数据包唯一性，同时优化时间戳索引效率。

二、解题思路

“队列+哈希表+时间戳索引”的组合策略：

1. 队列（packetQueue）：按时间戳顺序存储数据包，头部为最早待转发数据；

2. 哈希表（packetSet）：键为拼接的源-目标-时间戳，快速判定重复；

3. 时间戳索引（destTimeMap）：按目标地址分组，维护每个地址的时间戳有序列表，便于O(logN)删除操作。

内存超限时，从队列头部弹出数据包并同步更新哈希表与索引；添加新包时，利用upper_bound插入保持有序，降低维护成本。

三、解题步骤

1. 初始化：构造函数接收内存容量，初始化队列、哈希表及索引映射。

2. 添加数据包（addPacket）：

○ 生成唯一键，若存在则直接返回false；

○ 若队列超容，弹出头部包并删除对应键及时间戳索引；

○ 插入新包至队列，更新哈希表与目标地址的时间戳列表。

3. 转发数据包（forwardPacket）：

○ 若队列为空则返回空向量；

○ 弹出头部包，删除对应键及时间戳索引，返回包信息。

4. 时间戳维护：利用lower_bound定位待删时间戳，结合erase实现精准删除，避免遍历。

四、代码与注释

class Router {
private:
    struct Packet {
        int src;
        int dest;
        int ts;
    };
    
    int capacity;
    queue<Packet> packetQueue;
    unordered_set<string> packetSet;
    unordered_map<int, vector<int>> destTimeMap;
    
    string makeKey(int src, int dest, int ts) {
        return to_string(src)+","+to_string(dest)+","+to_string(ts);
    }
public:
    Router(int memoryLimit) : capacity(memoryLimit) {} // 初始化容量
    
    bool addPacket(int src, int dest, int ts) {
        string key = makeKey(src, dest, ts); // 生成唯一键
        if (packetSet.count(key)) return false; // 重复包过滤
        
        // 处理内存限制
        while (packetQueue.size() >= capacity) {
            auto p = packetQueue.front(); // 获取最早包
            string oldKey = makeKey(p.src, p.dest, p.ts);
            packetSet.erase(oldKey); // 删除哈希表记录
            
            // 从索引中删除对应时间戳
            auto& times = destTimeMap[p.dest];
            auto it = lower_bound(times.begin(), times.end(), p.ts);
            if (it!= times.end() && *it == p.ts) {
                times.erase(it); // 精准删除
            }
            packetQueue.pop(); // 弹出旧包
        }
        
        // 添加新数据包
        packetQueue.push({src, dest, ts});
        packetSet.insert(key);
        auto& times = destTimeMap[dest];
        auto it = upper_bound(times.begin(), times.end(), ts);
        times.insert(it, ts); // 有序插入时间戳
        return true;
    }
    
    vector<int> forwardPacket() {
        if (packetQueue.empty()) return {}; // 空队列直接返回
        
        auto p = packetQueue.front();
        string key = makeKey(p.src, p.dest, p.ts);
        packetSet.erase(key); // 删除哈希表记录
        
        // 更新索引
        auto& times = destTimeMap[p.dest];
        auto it = lower_bound(times.begin(), times.end(), p.ts);
        if (it!= times.end() && *it == p.ts) {
            times.erase(it);
        }
        packetQueue.pop(); // 弹出已转发包
        return {p.src, p.dest, p.ts}; // 返回包信息
    }
    int getCount(int dest, int start, int end) {
        if (!destTimeMap.count(dest)) return 0;
        
        const auto& times = destTimeMap[dest];
        auto left = lower_bound(times.begin(), times.end(), start);
        auto right = upper_bound(times.begin(), times.end(), end);
        return right - left;
    }
};