{"id":6695,"date":"2020-05-03T20:51:18","date_gmt":"2020-05-04T03:51:18","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6695"},"modified":"2020-05-03T20:51:28","modified_gmt":"2020-05-04T03:51:28","slug":"leetcode-1436-destination-city","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1436-destination-city\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1436. Destination City"},"content":{"rendered":"\n

You are given the array paths<\/code>, where paths[i] = [cityAi<\/sub>, cityBi<\/sub>]<\/code> means there exists a direct path going from cityAi<\/sub><\/code> to cityBi<\/sub><\/code>. Return the destination city, that is, the city without any path outgoing to another city.<\/em><\/p>\n\n\n\n

It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> paths = [[\"London\",\"New York\"],[\"New York\",\"Lima\"],[\"Lima\",\"Sao Paulo\"]]\nOutput:<\/strong> \"Sao Paulo\" \nExplanation:<\/strong> Starting at \"London\" city you will reach \"Sao Paulo\" city which is the destination city. Your trip consist of: \"London\" -> \"New York\" -> \"Lima\" -> \"Sao Paulo\".\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> paths = [[\"B\",\"C\"],[\"D\",\"B\"],[\"C\",\"A\"]]\nOutput:<\/strong> \"A\"\nExplanation:<\/strong> All possible trips are: \n\"D\" -> \"B\" -> \"C\" -> \"A\". \n\"B\" -> \"C\" -> \"A\". \n\"C\" -> \"A\". \n\"A\". \nClearly the destination city is \"A\".\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> paths = [[\"A\",\"Z\"]]\nOutput:<\/strong> \"Z\"\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= paths.length <= 100<\/code><\/li>
  • paths[i].length == 2<\/code><\/li>
  • 1 <= cityAi<\/sub>.length, cityBi<\/sub>.length <= 10<\/code><\/li>
  • cityAi <\/sub>!= cityBi<\/sub><\/code><\/li>
  • All strings consist of lowercase and uppercase English letters and the space character.<\/li><\/ul>\n\n\n\n
    Solution: Count in \/ out degree for each node<\/strong><\/h2>\n\n\n\n
    Note: this is a more general solution to this type of problems.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(n)<\/p>\n\n\n\n
    Destination City: in_degree == 1 and out_degree == 0<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  string destCity(vector>& paths) {\n    unordered_map in, out;\n    for (const auto& path : paths) {\n      ++out[path[0]];\n      ++in[path[1]];\n    }\n    \n    for (const auto& [city, degree] : in)\n      if (degree == 1 && out[city] == 0) return city;\n    \n    return \"\";\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi. Return the destination city, that is, the city without any path…<\/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":[222,77,82],"class_list":["post-6695","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-easy","tag-graph","tag-hashtable","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6695","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=6695"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6695\/revisions"}],"predecessor-version":[{"id":6697,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6695\/revisions\/6697"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6695"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6695"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6695"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}