題目
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 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 <= 100paths[i].length == 21 <= cityAi.length, cityBi.length <= 10cityAi != 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