力扣3508题：队列+哈希解决模拟路由器

2天前力扣题解52

一、题目解读

力扣3508题要求实现一个具有内存限制的路由器模拟系统，主要考察数据结构设计能力。题目涉及三大核心操作：添加数据包(adDPacket)、转发数据包(forwardPacket)和按条件统计数据包(getCount)，需要高效处理数据包去重、内存溢出和时间范围查询等问题。

二、解题思路

采用"队列+哈希集合+有序映射"的复合数据结构：

队列管理：使用queue实现FIFO缓存淘汰机制
快速去重：通过unordered_set存储数据包唯一标识
高效统计：利用unordered_map维护目标地址到有序时间戳数组的映射
二分优化：在时间范围查询时使用lower_bound/upper_bound实现O(logn)复杂度

三、解题步骤

初始化阶段：构建Router类，初始化容量和三个核心数据结构
添加数据包：

生成唯一key检查重复
处理内存溢出（队列满时移除头部元素）
维护目标地址的时间戳有序数组

转发数据包：从队列头部取出元素，同步更新其他数据结构
统计查询：使用二分查找快速定位时间范围内的数据包数量

四、完整代码实现

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;
    }
};