題目及要求

給你一份旅游線路圖，該線路圖中的旅行線路用數組 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示該線路將會從 cityAi 直接前往 cityBi 。請你找出這次旅行的終點站，即沒有任何可以通往其他城市的線路的城市。

題目數據保證線路圖會形成一條不存在循環的線路，因此恰有一個旅行終點站。

示例 1：

輸入：paths = [[“London”,“New York”],[“New York”,“Lima”],[“Lima”,“Sao Paulo”]]
輸出：“Sao Paulo”
解釋：從 “London” 出發，最后抵達終點站 “Sao Paulo” 。本次旅行的路線是 “London” -> “New York” -> “Lima” -> “Sao Paulo” 。
示例 2：

輸入：paths = [[“B”,“C”],[“D”,“B”],[“C”,“A”]]
輸出：“A”
解釋：所有可能的線路是：
“D” -> “B” -> “C” -> “A”.
“B” -> “C” -> “A”.
“C” -> “A”.
“A”.
顯然，旅行終點站是 “A” 。
示例 3：

輸入：paths = [[“A”,“Z”]]
輸出：“Z”

提示：

1 <= paths.length <= 100
paths[i].length == 2
1 <= cityAi.length, cityBi.length <= 10
cityAi != cityBi
所有字符串均由大小寫英文字母和空格字符組成。

哈希算法

思路：我們首先使用unordered_set startCities來記錄所有出現過的起始城市，然后再次遍歷paths，對于每條路徑p，如果它的目標城市p[1]不在startCities中，即沒有作為起始城市出現過，那么直接返回該目標城市作為結果。

class Solution {
public:string destCity(vector<vector<string>>& paths) {//用于存儲所有起始城市。unordered_set<string> startCities;// 遍歷路徑數組，將每個路徑的起始城市添加到集合中。for (auto p : paths) {startCities.insert(p[0]);}// 再次遍歷路徑數組，對于每個路徑，如果目的城市在 startCities 集合中不存在，說明該城市只作為終點，沒有作為起點，因此將其作為結果返回。for (auto p : paths) {if (startCities.find(p[1]) == startCities.end()) {return p[1];}}// 如果遍歷完所有路徑后都沒有找到符合條件的目的地城市，則返回空字符串。return "";}
};

在main內使用

int main() {// 創建一個 Solution 對象Solution solution;// 創建一個包含路徑的二維字符串數組vector<vector<string>> paths = {{"A", "B"}, {"B", "C"}, {"C", "D"}, {"D", "E"}};// 調用 destCity 函數來找到目的地城市string destination = solution.destCity(paths);// 打印結果cout << "終點是： " << destination << endl;return 0;
}