{"id":6543,"date":"2020-03-28T21:35:17","date_gmt":"2020-03-29T04:35:17","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6543"},"modified":"2020-03-28T21:37:46","modified_gmt":"2020-03-29T04:37:46","slug":"leetcode-1396-design-underground-system","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1396-design-underground-system\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1396. Design Underground System"},"content":{"rendered":"\n<p>Implement the class&nbsp;<code>UndergroundSystem<\/code>&nbsp;that supports three methods:<\/p>\n\n\n\n<p>1.<code>&nbsp;checkIn(int id, string stationName, int t)<\/code><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>A customer with id card equal to&nbsp;<code>id<\/code>, gets in the station&nbsp;<code>stationName<\/code>&nbsp;at time&nbsp;<code>t<\/code>.<\/li><li>A customer&nbsp;can only be checked into one place at a time.<\/li><\/ul>\n\n\n\n<p>2.<code>&nbsp;checkOut(int id, string stationName, int t)<\/code><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>A customer with id card equal to&nbsp;<code>id<\/code>, gets out from the station&nbsp;<code>stationName<\/code>&nbsp;at time&nbsp;<code>t<\/code>.<\/li><\/ul>\n\n\n\n<p>3.&nbsp;<code>getAverageTime(string startStation, string endStation)<\/code>&nbsp;<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Returns the average time to travel between the&nbsp;<code>startStation<\/code>&nbsp;and the&nbsp;<code>endStation<\/code>.<\/li><li>The average time is computed from all the previous traveling from&nbsp;<code>startStation<\/code>&nbsp;to&nbsp;<code>endStation<\/code>&nbsp;that happened&nbsp;<strong>directly<\/strong>.<\/li><li>Call to&nbsp;<code>getAverageTime<\/code>&nbsp;is always valid.<\/li><\/ul>\n\n\n\n<p>You can assume all calls to&nbsp;<code>checkIn<\/code>&nbsp;and&nbsp;<code>checkOut<\/code>&nbsp;methods are consistent. That is, if a customer gets in at time&nbsp;<strong>t<sub>1<\/sub><\/strong>&nbsp;at some station, then it gets out at time&nbsp;<strong>t<sub>2<\/sub><\/strong>&nbsp;with&nbsp;<strong>t<sub>2<\/sub>&nbsp;&gt; t<sub>1<\/sub><\/strong>.&nbsp;All events happen in chronological order.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input<\/strong>\n[\"UndergroundSystem\",\"checkIn\",\"checkIn\",\"checkIn\",\"checkOut\",\"checkOut\",\"checkOut\",\"getAverageTime\",\"getAverageTime\",\"checkIn\",\"getAverageTime\",\"checkOut\",\"getAverageTime\"]\n[[],[45,\"Leyton\",3],[32,\"Paradise\",8],[27,\"Leyton\",10],[45,\"Waterloo\",15],[27,\"Waterloo\",20],[32,\"Cambridge\",22],[\"Paradise\",\"Cambridge\"],[\"Leyton\",\"Waterloo\"],[10,\"Leyton\",24],[\"Leyton\",\"Waterloo\"],[10,\"Waterloo\",38],[\"Leyton\",\"Waterloo\"]]\n\n<strong>Output<\/strong>\n[null,null,null,null,null,null,null,14.0,11.0,null,11.0,null,12.0]\n\n<strong>Explanation<\/strong>\nUndergroundSystem undergroundSystem = new UndergroundSystem();\nundergroundSystem.checkIn(45, \"Leyton\", 3);\nundergroundSystem.checkIn(32, \"Paradise\", 8);\nundergroundSystem.checkIn(27, \"Leyton\", 10);\nundergroundSystem.checkOut(45, \"Waterloo\", 15);\nundergroundSystem.checkOut(27, \"Waterloo\", 20);\nundergroundSystem.checkOut(32, \"Cambridge\", 22);\nundergroundSystem.getAverageTime(\"Paradise\", \"Cambridge\");       \/\/ return 14.0. There was only one travel from \"Paradise\" (at time 8) to \"Cambridge\" (at time 22)\nundergroundSystem.getAverageTime(\"Leyton\", \"Waterloo\");          \/\/ return 11.0. There were two travels from \"Leyton\" to \"Waterloo\", a customer with id=45 from time=3 to time=15 and a customer with id=27 from time=10 to time=20. So the average time is ( (15-3) + (20-10) ) \/ 2 = 11.0\nundergroundSystem.checkIn(10, \"Leyton\", 24);\nundergroundSystem.getAverageTime(\"Leyton\", \"Waterloo\");          \/\/ return 11.0\nundergroundSystem.checkOut(10, \"Waterloo\", 38);\nundergroundSystem.getAverageTime(\"Leyton\", \"Waterloo\");          \/\/ return 12.0<\/p>\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>There will be at most&nbsp;<code>20000<\/code>&nbsp;operations.<\/li><li><code>1 &lt;= id, t &lt;= 10^6<\/code><\/li><li>All strings consist of uppercase, lowercase English letters and digits.<\/li><li><code>1 &lt;=&nbsp;stationName.length &lt;= 10<\/code><\/li><li>Answers within&nbsp;<code>10^-5<\/code>&nbsp;of the actual value will be accepted as correct.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Hashtable<\/strong><\/h2>\n\n\n\n<p>For each user, store the checkin station and time.<br>For each trip (startStation + &#8220;_&#8221; + endStation), store the total time and counts.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass UndergroundSystem {\npublic:\n  UndergroundSystem() {}\n\n  void checkIn(int id, string stationName, int t) {\n    m_[id] = {stationName, t};\n  }\n\n  void checkOut(int id, string stationName, int t) {\n    const auto& [s0, t0] = m_[id];\n    string key = s0 + \"_\" + stationName;\n    times_[key].first += (t - t0);\n    ++times_[key].second;\n  }\n\n  double getAverageTime(string startStation, string endStation) {\n    const auto& [sum, count] = times_[startStation + \"_\" + endStation];\n    return static_cast<double>(sum) \/ count;\n  }\nprivate:\n  unordered_map<int, pair<string, int>> m_; \/\/ id -> {station, t}\n  unordered_map<string, pair<int, int>> times_; \/\/ trip -> {sum, count}\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Implement the class&nbsp;UndergroundSystem&nbsp;that supports three methods: 1.&nbsp;checkIn(int id, string stationName, int t) A customer with id card equal to&nbsp;id, gets in the station&nbsp;stationName&nbsp;at time&nbsp;t. A&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[369,251,82,177],"class_list":["post-6543","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-class","tag-design","tag-hashtable","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6543","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=6543"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6543\/revisions"}],"predecessor-version":[{"id":6545,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6543\/revisions\/6545"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6543"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6543"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6543"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}