{"id":10353,"date":"2025-04-15T19:18:19","date_gmt":"2025-04-16T02:18:19","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=10353"},"modified":"2025-04-15T19:26:26","modified_gmt":"2025-04-16T02:26:26","slug":"leetcode-3508-implement-router","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/uncategorized\/leetcode-3508-implement-router\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 3508. Implement Router"},"content":{"rendered":"\n<p>\u7b97\u662f\u6bd4\u8f83\u590d\u6742\u7684\u9898\u76ee\u4e86\uff0c\u4e3b\u8981\u8003\u5bdf\u6570\u636e\u7ed3\u6784\u7684\u9009\u62e9\u548c\u5e94\u7528\u3002<\/p>\n\n\n\n<p><strong>Note<\/strong>\u00a0that queries for\u00a0<code>addPacket<\/code>\u00a0will be made in increasing order of\u00a0<code>timestamp<\/code>.<br>\u628a\u9898\u76ee\u7b80\u5316\u4e86\u4e0d\u5c11\uff0c\u6ce8\u610ftimestamp\u53ef\u80fd\u4f1a\u60f3\u540c\uff0c\u975e\u4e25\u683c\u5355\u8c03\u9012\u589e\u3002<\/p>\n\n\n\n<p>forwardPacket \u7684 FIFO\uff0c\u9700\u8981deque\u6216\u8005list<br>getCount \u7279\u5b9akey\u7684\u8303\u56f4\u67e5\u8be2\uff0chashmap + vector \/ deque<br>addPacket \u9700\u8981\u7528hashtable \u53bb\u91cd\u3002\u8fd8\u8981remove\u6700\u65e7\u7684packet\uff0c\u6700\u540e\u7684\u9009\u62e9\u843d\u5230\u7684deque\u4e0a\u3002<\/p>\n\n\n\n<p>deque\u4e24\u5934\u53ef\u4ee5\u6dfb\u52a0\/\u5220\u9664\uff0c\u8fd8\u80fdrandom access\u505a\u4e8c\u5206\u641c\u7d22\uff0c\u771f\u662f\u5c45\u5bb6\u65c5\u884c\u5fc5\u5907\u4e4b\u6570\u636e\u7ed3\u6784\u3002<\/p>\n\n\n\n<p>\u65f6\u95f4\u590d\u6742\u5ea6\uff1aaddPacket: O(1)\uff0cforwardPacket\uff1aO(1)\uff0cgetCount\uff1aO(logN) N\u4e3adst\u7684packet\u6570\u91cf\u3002<br>\u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO(M)<\/p>\n\n\n\n<pre lang=\"c++\">\nclass Router {\npublic:\n  Router(int memoryLimit): memoryLimit_{memoryLimit}, size_{0} {\n    \n  }\n  \n  bool addPacket(int source, int destination, int timestamp) {\n    if (!p_.insert(getKey(source, destination, timestamp)).second){\n      return false;\n    }\n\n    if (size_ == memoryLimit_) {\n      forwardPacket(); \/\/ remove the oldest.\n    }\n\n    packets_.emplace_back(source, destination, timestamp);\n    c_[destination].emplace_back(timestamp);\n\n    ++size_;\n    return true;\n  }\n  \n  vector<int> forwardPacket() {\n    if (size_ == 0) return {};\n    auto [src, dst, timestamp] = packets_.front();\n    packets_.pop_front();\n    --size_;\n    c_[dst].pop_front();\n    p_.erase(getKey(src, dst, timestamp));\n    return {src, dst, timestamp};\n  }\n  \n  int getCount(int destination, int startTime, int endTime) {\n    if (!c_.count(destination)) return 0;\n    const auto& q = c_[destination];\n    auto it1 = lower_bound(begin(q), end(q), startTime);\n    auto it2 = upper_bound(begin(q), end(q), endTime);\n    return it2 - it1;\n  }\nprivate:\n  \/\/ https:\/\/zxi.mytechroad.com\/blog\/uncategorized\/leetcode-3508-implement-router\/\n  string getKey(int s, int d, int t) {\n    return to_string(s) + \"_\" + to_string(d) + \"_\" + to_string(t);\n  }\n  int memoryLimit_;\n  int size_;\n  unordered_set<string> p_; \/\/ {f'{src}_{dst}_{timestamp}'}\n  deque<tuple<int, int, int>> packets_; \/\/ {{src, dst, timestamp}}\n  unordered_map<int, deque<int>> c_; \/\/ {dst -> timestamp}\n};\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u7b97\u662f\u6bd4\u8f83\u590d\u6742\u7684\u9898\u76ee\u4e86\uff0c\u4e3b\u8981\u8003\u5bdf\u6570\u636e\u7ed3\u6784\u7684\u9009\u62e9\u548c\u5e94\u7528\u3002 Note\u00a0that queries for\u00a0addPacket\u00a0will be made in increasing order of\u00a0timestamp.\u628a\u9898\u76ee\u7b80\u5316\u4e86\u4e0d\u5c11\uff0c\u6ce8\u610ftimestamp\u53ef\u80fd\u4f1a\u60f3\u540c\uff0c\u975e\u4e25\u683c\u5355\u8c03\u9012\u589e\u3002 forwardPacket \u7684 FIFO\uff0c\u9700\u8981deque\u6216\u8005listgetCount \u7279\u5b9akey\u7684\u8303\u56f4\u67e5\u8be2\uff0chashmap + vector \/ dequeaddPacket \u9700\u8981\u7528hashtable \u53bb\u91cd\u3002\u8fd8\u8981remove\u6700\u65e7\u7684packet\uff0c\u6700\u540e\u7684\u9009\u62e9\u843d\u5230\u7684deque\u4e0a\u3002 deque\u4e24\u5934\u53ef\u4ee5\u6dfb\u52a0\/\u5220\u9664\uff0c\u8fd8\u80fdrandom access\u505a\u4e8c\u5206\u641c\u7d22\uff0c\u771f\u662f\u5c45\u5bb6\u65c5\u884c\u5fc5\u5907\u4e4b\u6570\u636e\u7ed3\u6784\u3002 \u65f6\u95f4\u590d\u6742\u5ea6\uff1aaddPacket: O(1)\uff0cforwardPacket\uff1aO(1)\uff0cgetCount\uff1aO(logN) N\u4e3adst\u7684packet\u6570\u91cf\u3002\u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO(M)&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-10353","post","type-post","status-publish","format-standard","hentry","category-uncategorized","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10353","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=10353"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10353\/revisions"}],"predecessor-version":[{"id":10363,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10353\/revisions\/10363"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=10353"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=10353"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=10353"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}