Skip to content

LeetCode: 1436-Destination City 解題紀錄

Last Updated on 2023-12-15 by Clay

題目

You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBiReturn the destination city, that is, the city without any path outgoing to another city.

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

Example 1:Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]] Output: "Sao Paulo" Explanation: 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".

Example 2:Input: paths = [["B","C"],["D","B"],["C","A"]] Output: "A" Explanation: All possible trips are:  "D" -> "B" -> "C" -> "A".  "B" -> "C" -> "A".  "C" -> "A".  "A".  Clearly the destination city is "A".

Example 3:Input: paths = [["A","Z"]] Output: "Z"

Constraints:

  • 1 <= paths.length <= 100
  • paths[i].length == 2
  • 1 <= cityAi.length, cityBi.length <= 10
  • cityAi != cityBi
  • All strings consist of lowercase and uppercase English letters and the space character.

每個城市之間都有著單方向的通路,並且城市間的道路只會走一次。我們要判斷出最後抵達的城市是哪座並回傳。


解題思路

我使用一個字典儲存城市之間的關係。如果是從 A 城市出發,則 A += 1;若是 A 程式被抵達,則 A -= 1。

最後,目的地的城市只會被抵達一次,所以一定是 -1。當然,使用 set 也是同樣的概念。


C++ 範例程式碼

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        // Init
        unordered_map<string, int> counter;

        // Count
        for (vector<string>& path: paths) {
            ++counter[path[0]];
            --counter[path[1]];
        }

        // Get the destination
        for (auto& it: counter) {
            if (it.second == -1) {
                return it.first;
            }
        }

        return "";
    }
};



Python 範例程式碼

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        # Init
        counter = {}

        # Count
        for path in paths:
            counter[path[0]] = counter.get(path[0], 0) + 1
            counter[path[1]] = counter.get(path[1], 0) - 1

        # Find the destination
        for city in counter:
            if counter[city] == -1:
                return city

References


Read More

Leave a Reply