leetcode 1436 Destination City哈希集合与哈希映射双视角求解终点城市的实战指南【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文基于 leetcode 仓库中的解析文档 articles/destination-city.md系统讲解 LeetCode 1436 Destination City终点城市这道题的三套解法O(n²) 暴力枚举、O(n) 哈希集合与 O(n) 哈希映射链式追踪。读完后你将掌握如何用 HashSet 与 HashMap 这两种数据结构对城市-路径链建模并能直接在仓库中对照 java/1436-destination-city.java 与 kotlin/1436-destination-city.kt 两个已入库的参考实现将哈希表类题目的通用套路迁移到自己的代码中。题目描述与前置知识题目的输入是一个路径数组paths其中paths[i] [cityA, cityB]表示存在一条从cityA直接到达cityB的路径。要求找出终点城市——即只作为路径的终点第二个元素出现、而从未作为任何路径的起点第一个元素出现的城市。题目保证这样的城市恰好存在一个原文档指出 the problem guarantees one exists因此理论上找不到时返回空串只是防御性写法。动手之前需要先掌握两种数据结构Hash Set哈希集合提供 O(1) 的成员查找用于快速判断某个城市是否是一个起点Hash Map哈希映射用于把路径链建模为起点 → 终点的映射关系从而沿链追踪。解法一暴力枚举Brute Force核心思路终点城市是一个只作为终点出现、从不作为起点出现的城市。最直接的思路是对paths中的每一条路径取出其终点城市然后再次遍历所有路径检查该城市是否在任何路径中担任起点。第一个从不作为起点的终点即为答案。算法步骤遍历每条路径取出其终点城市paths[i][1]对该终点再次遍历所有路径检查它是否出现在某条路径的起点位置paths[j][0]若该终点在任何路径中都未作为起点出现则将其作为答案返回若遍历结束仍未找到题目保证存在正常不会走到返回空字符串。多语言实现以下实现完整继承自原文档覆盖 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言。Pythonclass Solution: def destCity(self, paths: List[List[str]]) - str: for i in range(len(paths)): flag True for j in range(len(paths)): if paths[i][1] paths[j][0]: flag False break if flag: return paths[i][1] return Javapublic class Solution { public String destCity(ListListString paths) { for (int i 0; i paths.size(); i) { boolean flag true; for (int j 0; j paths.size(); j) { if (paths.get(i).get(1).equals(paths.get(j).get(0))) { flag false; break; } } if (flag) { return paths.get(i).get(1); } } return ; } }注意 Java 版本使用equals比较字符串这是 Java 字符串比较的正确姿势直接比较的是引用而非内容。Cclass Solution { public: string destCity(vectorvectorstring paths) { for (int i 0; i paths.size(); i) { bool flag true; for (int j 0; j paths.size(); j) { if (paths[i][1] paths[j][0]) { flag false; break; } } if (flag) { return paths[i][1]; } } return ; } };JavaScriptclass Solution { /** * param {string[][]} paths * return {string} */ destCity(paths) { for (let i 0; i paths.length; i) { let flag true; for (let j 0; j paths.length; j) { if (paths[i][1] paths[j][0]) { flag false; break; } } if (flag) { return paths[i][1]; } } return ; } }C#public class Solution { public string DestCity(IListIListstring paths) { for (int i 0; i paths.Count; i) { bool flag true; for (int j 0; j paths.Count; j) { if (paths[i][1] paths[j][0]) { flag false; break; } } if (flag) { return paths[i][1]; } } return ; } }C# 中字符串的是内容比较运算符因此无需Equals显式调用。Gofunc destCity(paths [][]string) string { for i : 0; i len(paths); i { flag : true for j : 0; j len(paths); j { if paths[i][1] paths[j][0] { flag false break } } if flag { return paths[i][1] } } return }Kotlinclass Solution { fun destCity(paths: ListListString): String { for (i in paths.indices) { var flag true for (j in paths.indices) { if (paths[i][1] paths[j][0]) { flag false break } } if (flag) { return paths[i][1] } } return } }Swiftclass Solution { func destCity(_ paths: [[String]]) - String { for i in 0..paths.count { var flag true for j in 0..paths.count { if paths[i][1] paths[j][0] { flag false break } } if flag { return paths[i][1] } } return } }Rustimpl Solution { pub fn dest_city(paths: VecVecString) - String { for i in 0..paths.len() { let mut flag true; for j in 0..paths.len() { if paths[i][1] paths[j][0] { flag false; break; } } if flag { return paths[i][1].clone(); } } String::new() } }Rust 版本因为String不能部分移动返回时需要clone()一份。复杂度分析时间复杂度$O(n^2)$ —— 对每个终点都要再扫一遍全部路径n 为路径条数空间复杂度$O(1)$ —— 除输入外仅使用常数个标记变量。暴力解法的价值在于它是定义直译适合先写出来确认题目理解无误再考虑优化。解法二哈希集合Hash Set核心思路暴力解法的瓶颈在于判断某个城市是否曾作为起点这一步是 O(n) 的线性扫描。把所有起点城市先放进一个哈希集合这一步把成员判断压缩到 O(1)任何一个不在起点集合里的终点城市就是我们要找的终点。算法步骤创建哈希集合把所有起点城市每条路径的第一个元素加入集合遍历所有路径检查每条路径的终点城市第二个元素若某个终点城市不在集合中立即将其作为答案返回第一个不在集合中的终点即为最终终点城市。多语言实现Pythonclass Solution: def destCity(self, paths: List[List[str]]) - str: s set() for p in paths: s.add(p[0]) for p in paths: if p[1] not in s: return p[1]Javapublic class Solution { public String destCity(ListListString paths) { SetString s new HashSet(); for (ListString p : paths) { s.add(p.get(0)); } for (ListString p : paths) { if (!s.contains(p.get(1))) { return p.get(1); } } return ; } }Cclass Solution { public: string destCity(vectorvectorstring paths) { unordered_setstring s; for (auto p : paths) { s.insert(p[0]); } for (auto p : paths) { if (s.find(p[1]) s.end()) { return p[1]; } } return ; } };C 使用unordered_set配合find(...) end()判断避免operator[]的插入语义。JavaScriptclass Solution { /** * param {string[][]} paths * return {string} */ destCity(paths) { const s new Set(); for (const p of paths) { s.add(p[0]); } for (const p of paths) { if (!s.has(p[1])) { return p[1]; } } return ; } }C#public class Solution { public string DestCity(IListIListstring paths) { HashSetstring s new HashSetstring(); foreach (var p in paths) { s.Add(p[0]); } foreach (var p in paths) { if (!s.Contains(p[1])) { return p[1]; } } return ; } }Gofunc destCity(paths [][]string) string { s : make(map[string]bool) for _, p : range paths { s[p[0]] true } for _, p : range paths { if !s[p[1]] { return p[1] } } return }Go 没有内置 Set惯用map[string]bool模拟。注意!s[p[1]]利用了缺失键返回零值false的特性恰好等价于不在集合中。Kotlinclass Solution { fun destCity(paths: ListListString): String { val s HashSetString() for (p in paths) { s.add(p[0]) } for (p in paths) { if (p[1] !in s) { return p[1] } } return } }Kotlin 的!in是contains的否定语法糖可读性很好。Swiftclass Solution { func destCity(_ paths: [[String]]) - String { var s SetString() for p in paths { s.insert(p[0]) } for p in paths { if !s.contains(p[1]) { return p[1] } } return } }Rustimpl Solution { pub fn dest_city(paths: VecVecString) - String { let s: HashSetstr paths.iter().map(|p| p[0].as_str()).collect(); for p in paths { if !s.contains(p[1].as_str()) { return p[1].clone(); } } String::new() } }Rust 版本用str切片构建集合以避免拷贝字符串是所有权语义下的常用技巧。复杂度分析时间复杂度$O(n)$ —— 建集合与遍历终点各为一次线性扫描哈希操作均摊 O(1)空间复杂度$O(n)$ —— 集合最多存储 n 个起点城市。仓库源码印证这套哈希集合解法正是本仓库已入库的两个参考解法所采用的方案。Java 实现 java/1436-destination-city.java 的核心逻辑为SetString set new HashSet(); for(ListString path: paths){ String city path.get(0); set.add(city); } for(ListString path: paths){ String city path.get(1); if(!set.contains(city)) return city; } return ;Kotlin 实现 kotlin/1436-destination-city.kt 同样是起点入集合 终点查集合的两段式结构并额外用一个默认值变量res paths[0][1]承担遍历结束未命中的兜底返回var fromCity: HashSetString hashSetOf() for (path in paths) fromCity.add(path[0]) var res paths[0][1] for (path in paths) { if (path[1] !in fromCity) { res path[1] break } } return res两个实现与本文解法二的算法步骤逐条对应可以直接作为提交 LeetCode 的成品参考。解法三哈希映射链式追踪Hash Map Chain核心思路换一个角度把路径数组看作一条单向链每个城市指向它的下一站。用哈希映射建立起点 → 终点的索引后从第一条路径的起点出发不断跳指针当某个城市在映射中找不到出边时它就是终点——因为终点城市没有任何出发的路径。算法步骤构建哈希映射键为起点城市值为对应的终点城市取第一条路径的起点城市作为初始位置沿链推进只要当前城市仍是映射的键就移动到它对应的终点当前城市不再是映射的键时说明它没有出边将其作为终点城市返回。多语言实现Pythonclass Solution: def destCity(self, paths: List[List[str]]) - str: mp {p[0]: p[1] for p in paths} start paths[0][0] while start in mp: start mp[start] return startJavapublic class Solution { public String destCity(ListListString paths) { MapString, String mp new HashMap(); for (ListString p : paths) { mp.put(p.get(0), p.get(1)); } String start paths.get(0).get(0); while (mp.containsKey(start)) { start mp.get(start); } return start; } }Cclass Solution { public: string destCity(vectorvectorstring paths) { unordered_mapstring, string mp; for (auto p : paths) { mp[p[0]] p[1]; } string start paths[0][0]; while (mp.find(start) ! mp.end()) { start mp[start]; } return start; } };JavaScriptclass Solution { /** * param {string[][]} paths * return {string} */ destCity(paths) { const mp new Map(); for (const p of paths) { mp.set(p[0], p[1]); } let start paths[0][0]; while (mp.has(start)) { start mp.get(start); } return start; } }C#public class Solution { public string DestCity(IListIListstring paths) { Dictionarystring, string mp new Dictionarystring, string(); foreach (var p in paths) { mp[p[0]] p[1]; } string start paths[0][0]; while (mp.ContainsKey(start)) { start mp[start]; } return start; } }Gofunc destCity(paths [][]string) string { mp : make(map[string]string) for _, p : range paths { mp[p[0]] p[1] } start : paths[0][0] for { if next, ok : mp[start]; ok { start next } else { break } } return start }Go 使用for {} 双返回值next, ok的模式实现可查键的循环这是 Go 处理 map 查询的惯用法。Kotlinclass Solution { fun destCity(paths: ListListString): String { val mp HashMapString, String() for (p in paths) { mp[p[0]] p[1] } var start paths[0][0] while (start in mp) { start mp[start]!! } return start } }Kotlin 中mp[start]返回可空类型!!断言非空是因为start in mp已经保证键存在。Swiftclass Solution { func destCity(_ paths: [[String]]) - String { var mp [String: String]() for p in paths { mp[p[0]] p[1] } var start paths[0][0] while let next mp[start] { start next } return start } }Swift 用while let绑定可选值一行同时完成查键 取值 判空是三种解法中 Swift 版本写得最简洁的一种。Rustimpl Solution { pub fn dest_city(paths: VecVecString) - String { let mp: HashMapstr, str paths .iter() .map(|p| (p[0].as_str(), p[1].as_str())) .collect(); let mut start paths[0][0].as_str(); while let Some(next) mp.get(start) { start next; } start.to_string() } }复杂度分析时间复杂度$O(n)$ —— 建映射 O(n) 沿链最多走 n 步空间复杂度$O(n)$ —— 映射存储 n 条边。与解法二的细微差别从源码结构看两种 O(n) 解法的时间与空间复杂度相同但侧重点不同Hash Set 解法回答哪个终点没有出边只需存在性判断数据结构最轻只存键Hash Map 解法回答从起点一路走到哪停天然保留了路径方向信息更贴近这道题的图论直觉每个节点出度至多为 1 的功能图也更容易推广到从任意指定城市出发求终点这类变体。常见陷阱Common Pitfalls原文档专门总结了两个高频错误写法值得逐条对照自查。陷阱一把两个城市都加入集合使用哈希集合时只有起点城市应该入集合。如果顺手把每条路径的两个端点都塞进去集合就同时包含起终点终点不在起点集合中这一判定条件随之失效所有终点都会命中集合最终必然落入兜底的空串返回。# Wrong - adds both cities for p in paths: s.add(p[0]) s.add(p[1]) # Incorrect: this includes destinations # Correct - only add starting cities for p in paths: s.add(p[0])陷阱二把检查方向搞反另一个常见逻辑错误是方向颠倒构建终点集合后去检查起点是否缺席寻找没有入边的城市而题目要找的是没有出边的城市。# Wrong - checking the wrong direction s set(p[1] for p in paths) # Set of destinations for p in paths: if p[0] not in s: # Looking for start with no incoming path return p[0] # Correct - find destination with no outgoing path s set(p[0] for p in paths) # Set of starting cities for p in paths: if p[1] not in s: # Destination that is never a start return p[1]一句话记忆集合装起点检查的对象是终点——终点缺席起点集合即为答案。三种解法对比与选型建议解法时间复杂度空间复杂度数据结构适用场景暴力枚举$O(n^2)$$O(1)$无确认题意、数据量极小时哈希集合$O(n)$$O(n)$Set只需判断某城市是否为起点最常用哈希映射链式追踪$O(n)$$O(n)$Map需要沿路径方向追踪、或题目变体涉及从指定城市出发对本仓库 README.md 所收录的这类哈希表入门题Arrays Hashing 专题推荐以解法二作为默认实现代码量最小、意图最清晰且与仓库中 java/1436-destination-city.java、kotlin/1436-destination-city.kt 两个已通过的参考实现完全一致解法三则作为理解路径即映射思想的进阶视角保留在工具箱中。延伸参考完整多语言解析原文articles/destination-city.mdJava 参考解法java/1436-destination-city.javaKotlin 参考解法kotlin/1436-destination-city.kt文章写作规范每题需含至少一种解法、复杂度分析、覆盖尽可能多的解法articles/README.md贡献新解法的命名与提交规范CONTRIBUTING.md【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考