旅行的终点站
- 题目及要求
- 哈希算法
- 在main内使用
题目及要求
给你一份旅游线路图,该线路图中的旅行线路用数组 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;
}