算是比较复杂的题目了，主要考察数据结构的选择和应用。
Note that queries for addPacket will be made in increasing order of timestamp.
把题目简化了不少，注意timestamp可能会想同，非严格单调递增。
forwardPacket 的 FIFO，需要deque或者list
getCount 特定key的范围查询，hashmap + vector / deque
addPacket 需要用hashtable 去重。还要remove最旧的packet，最后的选择落到的deque上。
deque两头可以添加/删除，还能random access做二分搜索，真是居家旅行必备之数据结构。
时间复杂度：addPacket: O(1)，forwardPacket：O(1)，getCount：O(logN) N为dst的packet数量。
空间复杂度：O(M)
|
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 46 47 48 49 50 |
class Router { public: Router(int memoryLimit): memoryLimit_{memoryLimit}, size_{0} { } bool addPacket(int source, int destination, int timestamp) { if (!p_.insert(getKey(source, destination, timestamp)).second){ return false; } if (size_ == memoryLimit_) { forwardPacket(); // remove the oldest. } packets_.emplace_back(source, destination, timestamp); c_[destination].emplace_back(timestamp); ++size_; return true; } vector<int> forwardPacket() { if (size_ == 0) return {}; auto [src, dst, timestamp] = packets_.front(); packets_.pop_front(); --size_; c_[dst].pop_front(); p_.erase(getKey(src, dst, timestamp)); return {src, dst, timestamp}; } int getCount(int destination, int startTime, int endTime) { if (!c_.count(destination)) return 0; const auto& q = c_[destination]; auto it1 = lower_bound(begin(q), end(q), startTime); auto it2 = upper_bound(begin(q), end(q), endTime); return it2 - it1; } private: // https://zxi.mytechroad.com/blog/uncategorized/leetcode-3508-implement-router/ string getKey(int s, int d, int t) { return to_string(s) + "_" + to_string(d) + "_" + to_string(t); } int memoryLimit_; int size_; unordered_set<string> p_; // {f'{src}_{dst}_{timestamp}'} deque<tuple<int, int, int>> packets_; // {{src, dst, timestamp}} unordered_map<int, deque<int>> c_; // {dst -> timestamp} }; |