class Solution {
public:
string destCity(vector<vector<string>>& paths) {
}
};
1436. 旅行终点站
给你一份旅游线路图，该线路图中的旅行线路用数组 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原站题解
rust 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2024-10-08 09:27:53
use std::collections::HashSet;
impl Solution {
pub fn dest_city(paths: Vec<Vec<String>>) -> String {
let mut set_a = HashSet::with_capacity(paths.len());
let mut set_b = HashSet::new();
for p in paths {
let a = &p[0];
let b = &p[1];
set_b.remove(a); // a 一定不是答案
if !set_a.contains(b) { // b 有可能是答案
set_b.insert(b.clone());
}
set_a.insert(a.clone());
}
set_b.into_iter().next().unwrap()
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 3.6 MB, 提交时间: 2024-10-08 09:27:32
func destCity(paths [][]string) string {
setA := make(map[string]struct{}, len(paths))
setB := map[string]struct{}{}
for _, p := range paths {
a, b := p[0], p[1]
delete(setB, a) // a 一定不是答案
if _, ok := setA[b]; !ok { // b 有可能是答案
setB[b] = struct{}{}
}
setA[a] = struct{}{}
}
for b := range setB {
return b
}
return ""
}
java 解法, 执行用时: 3 ms, 内存消耗: 42.5 MB, 提交时间: 2024-10-08 09:27:18
class Solution {
public String destCity(List<List<String>> paths) {
Set<String> setA = new HashSet<>(paths.size());
Set<String> setB = new HashSet<>();
for (List<String> p : paths) {
String a = p.get(0);
String b = p.get(1);
setB.remove(a); // a 一定不是答案
if (!setA.contains(b)) { // b 有可能是答案
setB.add(b);
}
setA.add(a);
}
return setB.iterator().next();
}
}
python3 解法, 执行用时: 39 ms, 内存消耗: 16.6 MB, 提交时间: 2024-10-08 09:26:59
class Solution:
def destCity(self, paths: List[List[str]]) -> str:
set_a = set()
set_b = set()
for a, b in paths:
set_b.discard(a) # a 一定不是答案
if b not in set_a: # b 有可能是答案
set_b.add(b)
set_a.add(a)
return set_b.pop()
python3 解法, 执行用时: 37 ms, 内存消耗: 16.3 MB, 提交时间: 2024-10-08 09:26:24
class Solution:
def destCity(self, paths: List[List[str]]) -> str:
mp = {k:1 for k, _ in paths}
for _, v in paths:
if v not in mp:
return v
return ''
golang 解法, 执行用时: 4 ms, 内存消耗: 3.9 MB, 提交时间: 2021-06-08 11:03:11
func destCity(paths [][]string) string {
mp := make(map[string]struct{})
for _, path := range paths {
mp[path[0]] = struct{} {}
}
for _, path := range paths {
if _, ok := mp[path[1]]; !ok {
return path[1]
}
}
return ""
}