农业建设信息网站百度空间登录入口

题目及要求

给你一份旅游线路图，该线路图中的旅行线路用数组 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;
}