LC 1436. 旅行终点站
题目描述
这是 LeetCode 上的 1436. 旅行终点站 ,难度为 简单。
给你一份旅游线路图,该线路图中的旅行线路用数组 paths
表示,其中 paths[i] = [cityAi, cityBi]
表示该线路将会从 cityAi
直接前往 cityBi
。
请你找出这次旅行的终点站,即没有任何可以通往其他城市的线路的城市。
题目数据保证线路图会形成一条不存在循环的线路,因此恰有一个旅行终点站。
示例 1:1
2
3
4
5输入:paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
输出:"Sao Paulo"
解释:从 "London" 出发,最后抵达终点站 "Sao Paulo" 。本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。
示例 2:1
2
3
4
5
6
7
8
9
10输入:paths = [["B","C"],["D","B"],["C","A"]]
输出:"A"
解释:所有可能的线路是:
"D" -> "B" -> "C" -> "A".
"B" -> "C" -> "A".
"C" -> "A".
"A".
显然,旅行终点站是 "A" 。
示例 3:1
2
3输入:paths = [["A","Z"]]
输出:"Z"
提示:
- $1 <= paths.length <= 100$
- $paths[i].length = 2$
- $1 <= cityAi.length, cityBi.length <= 10$
cityAi != cityBi
- 所有字符串均由大小写英文字母和空格字符组成
模拟 + 哈希表
根据题意,我们可以取一个任意城市作为起点,然后使用 $paths$ 中的路线信息开始搜索,直到当前城市无法到达下一个城市,即是答案。
实现上,为了可以快速找到某个城市所能到达的城市,可以先使用哈希表对 $paths$ 中的路线信息进行预处理。
Java 代码:1
2
3
4
5
6
7
8
9class 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;
}
}
C++ 代码:1
2
3
4
5
6
7
8
9
10class Solution {
public:
string destCity(vector<vector<string>>& paths) {
unordered_map<string, string> map;
for (auto& p : paths) map[p[0]] = p[1];
string ans = paths[0][0];
while (map.find(ans) != map.end()) ans = map[ans];
return ans;
}
};
Python 代码:1
2
3
4
5
6
7class Solution:
def destCity(self, paths: List[List[str]]) -> str:
path_map = {p[0]: p[1] for p in paths}
ans = paths[0][0]
while ans in path_map:
ans = path_map[ans]
return ans
- 时间复杂度:$O(n)$
- 空间复杂度:$O(n)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1436
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
**
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!