英文原文
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.
中文题目
给你一份旅游线路图，该线路图中的旅行线路用数组 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 <= 100paths[i].length == 21 <= cityAi.length, cityBi.length <= 10cityAi != cityBi- 所有字符串均由大小写英文字母和空格字符组成。
通过代码
高赞题解
写在前面
祝大家国庆快乐 😊 吃好玩好 🍭🍰🚚🌊🎆
模拟 + 哈希表
根据题意，我们可以取一个任意城市作为起点，然后使用 $paths$ 中的路线信息开始搜索，直到当前城市无法到达下一个城市，即是答案。
实现上，为了可以快速找到某个城市所能到达的城市，可以先使用哈希表对 $paths$ 中的路线信息进行预处理。
代码：
[]class Solution { public String destCity(List<List<String>> ps) { Map<String, String> map = new HashMap<>(); for (List<String> p : ps) map.put(p.get(0), p.get(1)); String ans = ps.get(0).get(0); while (map.containsKey(ans)) ans = map.get(ans); return ans; } }
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$
最后
题太简单？不如 加练如下题目 去跳舞 💃🏻💃🏻
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 45313 | 55151 | 82.2% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
