1. 题目解析与核心思路Destination City 是 LeetCode 上一道关于旅行路径的图论基础题。题目给出一个路径列表 paths其中 paths[i] [cityA, cityB] 表示存在一条从 cityA 直接前往 cityB 的路线。要求找出这次旅行的终点站即没有任何出路的城市。1.1 题目示例分析示例输入 paths [[London,New York],[New York,Lima],[Lima,Sao Paulo]]示例输出 Sao Paulo这个示例中London → New YorkNew York → LimaLima → Sao PauloSao Paulo 没有作为起点出现因此是终点站。1.2 解题关键点终点站的定义在路径列表中只作为终点出现从不作为起点的城市数据特点题目保证路径形成一条不循环的链输入规模路径数量在1到100之间城市名由3到10个小写字母组成2. 解法思路与实现2.1 哈希表解法最优解这是最高效的解决方案时间复杂度O(n)空间复杂度O(n)。def destCity(paths): start_cities set() end_cities set() for path in paths: start_cities.add(path[0]) end_cities.add(path[1]) return (end_cities - start_cities).pop()实现步骤创建两个集合分别存储所有起点城市和终点城市遍历paths填充这两个集合终点城市集合减去起点城市集合剩下的就是只作为终点出现的城市注意使用集合的差集运算可以高效找到目标城市这是Python集合操作的优势。2.2 字典计数解法另一种思路是统计每个城市的出度和入度def destCity(paths): city_count {} for a, b in paths: city_count[a] city_count.get(a, 0) 1 city_count[b] city_count.get(b, 0) - 1 for city in city_count: if city_count[city] -1: return city这种方法起点城市计数1有出度终点城市计数-1有入度最终计数为-1的城市就是终点站2.3 暴力解法不推荐虽然能通过但时间复杂度O(n^2)def destCity(paths): for i in range(len(paths)): candidate paths[i][1] is_destination True for j in range(len(paths)): if paths[j][0] candidate: is_destination False break if is_destination: return candidate3. 算法分析与优化3.1 时间复杂度对比解法时间复杂度空间复杂度适用场景哈希表O(n)O(n)最优解字典计数O(n)O(n)可扩展性强暴力O(n^2)O(1)仅小规模数据3.2 边界条件处理需要考虑的特殊情况只有一条路径时直接返回终点城市城市名大小写问题题目已说明是小写字母路径为空题目保证至少有一条路径3.3 空间优化思路如果内存严格受限可以先遍历记录所有起点城市再次遍历检查终点城市是否在起点集合中这样只需要一个集合存储起点城市def destCity(paths): starts {path[0] for path in paths} for path in paths: if path[1] not in starts: return path[1]4. 同类题目拓展掌握这道题后可以尝试以下类似题目Find the Town Judge寻找法官Flower Planting With No Adjacent花园种植Minimum Number of Vertices to Reach All Nodes可达点的最小集合这些题目都涉及图的入度和出度概念解法思路相似。5. 实际应用场景这类算法在实际中有广泛应用交通路线规划确定终点车站工作流引擎找出最终状态节点依赖关系分析找出不被依赖的模块数据管道确定最终输出节点提示面试中遇到这类题可以先画出示意图帮助理解路径关系。6. 常见错误与调试新手容易犯的错误没有考虑城市可能重复出现的情况错误理解终点站的定义以为要找出度最多的城市使用列表而非集合导致查找效率低下忽略题目保证路径形成一条链的条件调试技巧打印中间变量检查集合内容用简单测试用例验证如只有2个城市的路径检查返回值类型是否符合要求7. 不同语言实现7.1 Java实现public String destCity(ListListString paths) { SetString starts new HashSet(); for (ListString path : paths) { starts.add(path.get(0)); } for (ListString path : paths) { if (!starts.contains(path.get(1))) { return path.get(1); } } return ; }7.2 C实现string destCity(vectorvectorstring paths) { unordered_setstring starts; for (auto path : paths) { starts.insert(path[0]); } for (auto path : paths) { if (starts.find(path[1]) starts.end()) { return path[1]; } } return ; }7.3 JavaScript实现var destCity function(paths) { const starts new Set(); for (const [a, b] of paths) { starts.add(a); } for (const [a, b] of paths) { if (!starts.has(b)) { return b; } } return ; };8. 进阶思考如果题目条件变化路径可能形成环需要检测环的存在多个可能的终点需要返回所有终点城市名可能重复需要更复杂的处理这些变化会使题目难度提升可能需要使用深度优先搜索(DFS)等更复杂的算法。我在实际刷题中发现这类题目虽然简单但很好地训练了对集合数据结构的运用能力。建议初学者多练习这类基础题培养算法思维。对于有经验的开发者可以思考如何将其应用于实际工程问题中。 LeetCode 1436题解析：哈希表在图论路径问题中的应用
1. 题目解析与核心思路Destination City 是 LeetCode 上一道关于旅行路径的图论基础题。题目给出一个路径列表 paths其中 paths[i] [cityA, cityB] 表示存在一条从 cityA 直接前往 cityB 的路线。要求找出这次旅行的终点站即没有任何出路的城市。1.1 题目示例分析示例输入 paths [[London,New York],[New York,Lima],[Lima,Sao Paulo]]示例输出 Sao Paulo这个示例中London → New YorkNew York → LimaLima → Sao PauloSao Paulo 没有作为起点出现因此是终点站。1.2 解题关键点终点站的定义在路径列表中只作为终点出现从不作为起点的城市数据特点题目保证路径形成一条不循环的链输入规模路径数量在1到100之间城市名由3到10个小写字母组成2. 解法思路与实现2.1 哈希表解法最优解这是最高效的解决方案时间复杂度O(n)空间复杂度O(n)。def destCity(paths): start_cities set() end_cities set() for path in paths: start_cities.add(path[0]) end_cities.add(path[1]) return (end_cities - start_cities).pop()实现步骤创建两个集合分别存储所有起点城市和终点城市遍历paths填充这两个集合终点城市集合减去起点城市集合剩下的就是只作为终点出现的城市注意使用集合的差集运算可以高效找到目标城市这是Python集合操作的优势。2.2 字典计数解法另一种思路是统计每个城市的出度和入度def destCity(paths): city_count {} for a, b in paths: city_count[a] city_count.get(a, 0) 1 city_count[b] city_count.get(b, 0) - 1 for city in city_count: if city_count[city] -1: return city这种方法起点城市计数1有出度终点城市计数-1有入度最终计数为-1的城市就是终点站2.3 暴力解法不推荐虽然能通过但时间复杂度O(n^2)def destCity(paths): for i in range(len(paths)): candidate paths[i][1] is_destination True for j in range(len(paths)): if paths[j][0] candidate: is_destination False break if is_destination: return candidate3. 算法分析与优化3.1 时间复杂度对比解法时间复杂度空间复杂度适用场景哈希表O(n)O(n)最优解字典计数O(n)O(n)可扩展性强暴力O(n^2)O(1)仅小规模数据3.2 边界条件处理需要考虑的特殊情况只有一条路径时直接返回终点城市城市名大小写问题题目已说明是小写字母路径为空题目保证至少有一条路径3.3 空间优化思路如果内存严格受限可以先遍历记录所有起点城市再次遍历检查终点城市是否在起点集合中这样只需要一个集合存储起点城市def destCity(paths): starts {path[0] for path in paths} for path in paths: if path[1] not in starts: return path[1]4. 同类题目拓展掌握这道题后可以尝试以下类似题目Find the Town Judge寻找法官Flower Planting With No Adjacent花园种植Minimum Number of Vertices to Reach All Nodes可达点的最小集合这些题目都涉及图的入度和出度概念解法思路相似。5. 实际应用场景这类算法在实际中有广泛应用交通路线规划确定终点车站工作流引擎找出最终状态节点依赖关系分析找出不被依赖的模块数据管道确定最终输出节点提示面试中遇到这类题可以先画出示意图帮助理解路径关系。6. 常见错误与调试新手容易犯的错误没有考虑城市可能重复出现的情况错误理解终点站的定义以为要找出度最多的城市使用列表而非集合导致查找效率低下忽略题目保证路径形成一条链的条件调试技巧打印中间变量检查集合内容用简单测试用例验证如只有2个城市的路径检查返回值类型是否符合要求7. 不同语言实现7.1 Java实现public String destCity(ListListString paths) { SetString starts new HashSet(); for (ListString path : paths) { starts.add(path.get(0)); } for (ListString path : paths) { if (!starts.contains(path.get(1))) { return path.get(1); } } return ; }7.2 C实现string destCity(vectorvectorstring paths) { unordered_setstring starts; for (auto path : paths) { starts.insert(path[0]); } for (auto path : paths) { if (starts.find(path[1]) starts.end()) { return path[1]; } } return ; }7.3 JavaScript实现var destCity function(paths) { const starts new Set(); for (const [a, b] of paths) { starts.add(a); } for (const [a, b] of paths) { if (!starts.has(b)) { return b; } } return ; };8. 进阶思考如果题目条件变化路径可能形成环需要检测环的存在多个可能的终点需要返回所有终点城市名可能重复需要更复杂的处理这些变化会使题目难度提升可能需要使用深度优先搜索(DFS)等更复杂的算法。我在实际刷题中发现这类题目虽然简单但很好地训练了对集合数据结构的运用能力。建议初学者多练习这类基础题培养算法思维。对于有经验的开发者可以思考如何将其应用于实际工程问题中。