1. 先看题目这条旅行线路到底在问什么第187场周赛的T1也就是编号1436的这道“旅行终点站”我印象还挺深。倒不是因为它难恰恰是因为它太简单了简单到很多人反而在它上面翻了车。LeetCode的周赛从T1开始就是抢时间的T1拖得越久后面三道题的心态崩得越快。而这道题就是典型的“会者不难难者不会”的代表。题目描述很直白给你一份旅游线路图用数组 paths 表示其中 paths[i] [cityAi, cityBi] 表示线路从 cityAi 直接前往 cityBi。要求找出这次旅行的终点站也就是没有任何可以通往其他城市的线路的那个城市。换句话说给定若干条有向边找出那个“只进不出”的节点。其实这就是一道有向图的基本功题目。虽然披着旅行线路的外衣但本质就是给你一堆 A-B 的边让你找出没有出边的那一个节点。文中出现的城市名是小写字母组成的字符串长度在1到10之间路径数量最多100条城市数量不会超过路径数加一。数据范围很小暴力解法甚至也能通过但优秀的解法应该做到 O(N) 时间、O(N) 空间。这道题适合谁去看呢一个是准备参加周赛、想在T1上稳住节奏的选手另一个是刚开始刷图论、还分不清入度和出度概念的初学者。哪怕你现在连“哈希集合”是什么都不太清楚读完这篇也能把这道题彻底吃透顺便建立起一套处理“找唯一特殊节点”类问题的思维模型。2. 核心思路终点站的本质是“没有出度”2.1 用图的角度看问题而不是死磕城市名拿到这题第一步要做的是把描述“翻译”成数据结构语言。paths 数组里每一项是 [A, B]意思就是有一条从 A 指向 B 的有向边。把所有城市抽象成节点所有线路抽象成有向边题目就变成了在一张有向图里找一个出度为0的节点。这个转换很重要因为一旦你把这个模型建立起来题目就基本解完了。什么叫出度就是一个节点作为起点出现的次数。终点站的定义是“没有任何可以通往其他城市的线路”翻译成图论语言就是“没有一个路径以它作为起点”换句话说它的出度是0。但是要注意一个细节终点站一定出现在某个路径的终点位置也就是说它的入度至少是1。这两个条件加在一起才是完整的判定标准一个城市如果从来没有作为起点出现过但作为终点出现过那它就是答案。只看“出度为0”还不够因为如果有一个城市从来没出现过它的出度也是0但它显然不是终点站。所以正确的判定方式是在 paths 里找到一个 cityBi它不在任何 cityAi 的集合里。2.2 三种解法从暴力到最优先说最暴力的思路遍历所有路径的终点对每个终点再去遍历一遍所有路径的起点看看它有没有“露脸”。这需要用两层循环时间复杂度 O(N^2)。题目里路径数量最多100所以哪怕用这个笨办法也能过但显然它不是我们在周赛里应该写出来的代码——T1讲究的是又快又稳O(N^2)虽然能过但没必要。稍微进阶一点的思路是统计每个城市的出度。用一个哈希表遍历所有 paths把每个 path[0] 的计数加一最后再遍历一次 paths找到 path[1] 的出度为0的那个城市。这个思路是对的复杂度降到了 O(N)空间 O(N)。最推荐的其实是基于哈希集合的写法先把所有起点放进一个 HashSet然后再遍历所有终点看哪个终点不在这个集合里它就是答案。这个写法比出度统计更简洁逻辑也更直接。它本质上利用了“终点站一定不在起点集合里”这个必要条件。整个过程只需要一遍遍历放起点一遍遍历找终点时间复杂度 O(N)空间复杂度 O(N)。2.3 复杂度与适用场景对比三种方法的对比可以这样看方法时间复杂度空间复杂度代码量推荐程度暴力双重循环O(N^2)O(1)很少不推荐哈希表统计出度O(N)O(N)中等可选哈希集合找不在起点中的终点O(N)O(N)最少强烈推荐你可能会问出度统计和哈希集合法看起来差不多为什么要选后者原因在于哈希集合法省去了“计数”这个中间状态。统计出度要维护每个城市的出现次数如果你只需要找“最后剩下的那个节点”用集合天然去重的特性反而更贴合题意。而且集合版的代码短写起来不容易出错在周赛的环境下代码越短出bug的概率越低。3. 多语言实现把思路写成不会出错的代码3.1 Python实现与细节Python 的代码可以写得非常紧凑。先把所有起点收集到一个集合里再找不在集合中的终点class Solution: def destCity(self, paths: List[List[str]]) - str: starts set() for path in paths: starts.add(path[0]) for path in paths: if path[1] not in starts: return path[1]如果你喜欢更 Pythonic 的风格也可以用集合推导式和 next 表达式一行搞定核心逻辑class Solution: def destCity(self, paths: List[List[str]]) - str: starts {path[0] for path in paths} return next(path[1] for path in paths if path[1] not in starts)这里面有几个值得注意的细节。第一Python 的 set 是无序且去重的你不需要担心里面出现重复的起点。第二next 函数在生成器找不到元素时会抛出 StopIteration 异常但题目保证一定存在唯一的终点站所以这里不会触发。第三如果你用的是 Python 老版本List 的 typing 注解要记得从 typing 模块导入但在现代 LeetCode 环境里直接用 list 也可以。我看到有些人会图省事直接统计所有城市出现的次数返回出现次数为1的城市。这个写法在大部分测试用例上都能过但它是错的后面我会专门讲这个坑。3.2 C和Java写法示例C 的思路完全一样用 unordered_set 存起点class Solution { public: string destCity(vectorvectorstring paths) { unordered_setstring starts; for (auto p : paths) { starts.insert(p[0]); } for (auto p : paths) { if (starts.find(p[1]) starts.end()) { return p[1]; } } return ; } };Java 的写法则要稍微注意一下泛型和 List 的取值方式class Solution { public String destCity(ListListString paths) { SetString starts new HashSet(); for (ListString p : paths) { starts.add(p.get(0)); } for (ListString p : paths) { if (!starts.contains(p.get(1))) { return p.get(1); } } return ; } }C 里 unordered_set 的 find 和 end 比较是标准操作要注意别把 insert 后的返回值弄混了。Java 里 HashSet 的 contains 方法时间复杂度是 O(1)所以整体思路和 Python 版完全一致。三个语言用的是同一套逻辑这就说明你真正需要掌握的是“把起点放入集合再从终点里找答案”这个模型而不是死记某一种语言的语法。3.3 边界条件和代码健壮性写完之后建议自己在脑子里跑两个极端情况。第一个是 paths 只有一条路线比如 [[A,B]]这时起点集合是 {A}终点 B 不在集合中直接返回 B没有任何问题。第二个是所有城市组成一条长链比如 [[A,B],[B,C],[C,D]]起点集合是 {A,B,C}终点集合是 {B,C,D}只有 D 不在起点集合里正确。还有一个小问题如果 paths 里出现了空数组怎么办题目描述中 paths[i] 是长度为2的数组但数据范围那里写的 0 paths[i].length 100 会让一些人多虑。在实际测试用例中paths[i] 一定是合法的一对城市名不需要额外判空。不过你要是想写得特别稳也可以在遍历时加上长度判断但这属于防御性编程周赛里不建议花这个时间。4. 实战复盘周赛里这道题最容易踩的坑4.1 常见错误与反例这道题最大的坑就是“统计所有城市出现次数返回只出现一次的城市”。很多新手会踩进去我当初第一次做这题也差点这么干。给你一个反例就明白了paths [[A,B],[C,A],[D,C]]这条线路是 D-C-A-B终点是 B。现在统计所有城市出现次数A 出现2次C 出现2次D 出现1次B 出现1次。如果按照“只出现一次”来判定D 和 B 都是候选答案但 D 是起点根本不是终点站。所以只看出现次数完全不靠谱必须区分一个城市是“作为起点出现”还是“作为终点出现”。另一个容易犯的错误是把思路搞反去找“不在任何终点里的起点”也就是想找起点站。注意题目问的是终点站不是起点站。虽然这两个问题对称但一不留神就会写反。找起点的做法是把所有终点放进集合然后返回不在集合中的起点。这道题的正确答案是反过来把所有起点放进集合返回不在集合中的终点。我见过有群友赛后复盘说自己的代码逻辑看起来完全没问题结果一提交就 WA仔细一看就是把 start 和 dest 的集合搞反了。4.2 周赛抢分策略周赛的 T1 通常是最简单的题目目标是在极短时间内 AC。根据我的经验这题的理想时间线是这样的读题30秒建模30秒写代码30秒跑示例验证20秒总用时控制在2分钟以内。如果你在 T1 上花了超过5分钟说明你需要加强“把文字描述翻译成数据结构”的练习。很多人一看到图论、路线、城市这些词就开始脑补复杂的DFS或拓扑排序。实际上你只要瞄一眼数据范围——paths 长度最多100——就该知道 T1 考的不是算法复杂度而是基本建模能力。在 T1 上使用 DFS 或者建邻接表属于典型的杀鸡用牛刀。不是说不行而是你花了更多时间写复杂代码反而增加了出错的概率。我的建议是周赛开始后先把四道题都扫一眼T1 直接按“哈希集合”套路秒掉把节约下来的时间留给后面的 T2 和 T3。因为周赛排名很大程度上取决于完成时间T1 的 AC 时间每慢一分钟排名都会往后掉一大截。4.3 快速自查清单做完这道题之后我会在提交前默念几个检查点是否把所有起点都加入了集合有没有漏掉最后一条路径返回的是终点而不是起点判断条件是不是path[1] not in starts如果 paths 长度为1代码能否正常返回唯一终点如果存在 A-B 和 B-A 这样的循环结果会怎样这个输入违反了题目“唯一终点”的约束所以不需要额外处理但你可以想想自己的代码在这种情况下会返回什么有助于加深理解。这个自查过程只需要10秒但对避免低级失误非常有效。特别是第四条我建议你多想想它不违反题意但能帮你理解出度和入度的关系。5. 从这道题延伸出去的图论思维5.1 入度出度模型在其他题目中的应用做完这道题如果只是记住“用set找终点”那就太可惜了。这道题背后藏着的是图论里非常基础也非常重要的入度出度模型。所谓入度就是有多少条边指向这个节点出度就是有多少条边从这个节点指出。很多看起来完全不同的题目最后都能归结为找入度或出度满足特定条件的节点。LeetCode 里非常出名的一道题——找小镇法官就是同一个模型。题目描述是小镇里有 N 个人法官不相信任何人所有人都信任法官。翻译成图论语言就是法官的入度是 N-1出度是0。你需要找到那个唯一同时满足这两个条件的节点。你看这和本道题“终点站入度至少1、出度为0”的判定方式何其相似。再比如拓扑排序中找入度为0的节点作为起点本质上也是在玩入度出度这套东西。所以当你把“旅行终点站”这道题吃透再去刷其它图论入门题你会发现自己能很快地辨认出题目背后的核心考点而不是被表面的故事包装迷惑。5.2 面试和工程中怎么迁移这套思路面试的时候这道题可以有很多变体。比如给你一份任务依赖列表每个任务依赖另一个任务让你找出最后的那个任务或者给你一组“先修课程”的二元组让你判断学习顺序。这些题目的本质都是图上的入度出度分析。工程上也有类似的场景。我实际开发中遇到过这样一个需求有一组服务调用链记录每条记录是 [调用方, 被调用方]需要找出整个调用链最末端那个服务。这不就是旅行终点站的翻版吗只不过把城市名换成了服务名把旅行线路换成了调用关系。这时候哈希集合的解法可以直接迁移过来连算法都不用改。所以我觉得做算法题的最高境界不是背题而是建立“题目特征到算法模型”的映射。看到“给一堆二元组找唯一特殊节点”脑子里立刻跳出“集合差值入度出度哈希表”这几个关键词那你刷这道题的时间就没有白费。这题给我最大的启发是简单题里往往藏着最常用的图论思维。不要因为 AC 了就急着做下一题停下来想一想为什么哈希集合能一步定位终点想一想如果路径再多100倍这题还能不能这么写。把这些想明白下次遇到 T1你就能做到看到题目的那一刻已经知道代码要怎么写了。
1. 先看题目这条旅行线路到底在问什么第187场周赛的T1也就是编号1436的这道“旅行终点站”我印象还挺深。倒不是因为它难恰恰是因为它太简单了简单到很多人反而在它上面翻了车。LeetCode的周赛从T1开始就是抢时间的T1拖得越久后面三道题的心态崩得越快。而这道题就是典型的“会者不难难者不会”的代表。题目描述很直白给你一份旅游线路图用数组 paths 表示其中 paths[i] [cityAi, cityBi] 表示线路从 cityAi 直接前往 cityBi。要求找出这次旅行的终点站也就是没有任何可以通往其他城市的线路的那个城市。换句话说给定若干条有向边找出那个“只进不出”的节点。其实这就是一道有向图的基本功题目。虽然披着旅行线路的外衣但本质就是给你一堆 A-B 的边让你找出没有出边的那一个节点。文中出现的城市名是小写字母组成的字符串长度在1到10之间路径数量最多100条城市数量不会超过路径数加一。数据范围很小暴力解法甚至也能通过但优秀的解法应该做到 O(N) 时间、O(N) 空间。这道题适合谁去看呢一个是准备参加周赛、想在T1上稳住节奏的选手另一个是刚开始刷图论、还分不清入度和出度概念的初学者。哪怕你现在连“哈希集合”是什么都不太清楚读完这篇也能把这道题彻底吃透顺便建立起一套处理“找唯一特殊节点”类问题的思维模型。2. 核心思路终点站的本质是“没有出度”2.1 用图的角度看问题而不是死磕城市名拿到这题第一步要做的是把描述“翻译”成数据结构语言。paths 数组里每一项是 [A, B]意思就是有一条从 A 指向 B 的有向边。把所有城市抽象成节点所有线路抽象成有向边题目就变成了在一张有向图里找一个出度为0的节点。这个转换很重要因为一旦你把这个模型建立起来题目就基本解完了。什么叫出度就是一个节点作为起点出现的次数。终点站的定义是“没有任何可以通往其他城市的线路”翻译成图论语言就是“没有一个路径以它作为起点”换句话说它的出度是0。但是要注意一个细节终点站一定出现在某个路径的终点位置也就是说它的入度至少是1。这两个条件加在一起才是完整的判定标准一个城市如果从来没有作为起点出现过但作为终点出现过那它就是答案。只看“出度为0”还不够因为如果有一个城市从来没出现过它的出度也是0但它显然不是终点站。所以正确的判定方式是在 paths 里找到一个 cityBi它不在任何 cityAi 的集合里。2.2 三种解法从暴力到最优先说最暴力的思路遍历所有路径的终点对每个终点再去遍历一遍所有路径的起点看看它有没有“露脸”。这需要用两层循环时间复杂度 O(N^2)。题目里路径数量最多100所以哪怕用这个笨办法也能过但显然它不是我们在周赛里应该写出来的代码——T1讲究的是又快又稳O(N^2)虽然能过但没必要。稍微进阶一点的思路是统计每个城市的出度。用一个哈希表遍历所有 paths把每个 path[0] 的计数加一最后再遍历一次 paths找到 path[1] 的出度为0的那个城市。这个思路是对的复杂度降到了 O(N)空间 O(N)。最推荐的其实是基于哈希集合的写法先把所有起点放进一个 HashSet然后再遍历所有终点看哪个终点不在这个集合里它就是答案。这个写法比出度统计更简洁逻辑也更直接。它本质上利用了“终点站一定不在起点集合里”这个必要条件。整个过程只需要一遍遍历放起点一遍遍历找终点时间复杂度 O(N)空间复杂度 O(N)。2.3 复杂度与适用场景对比三种方法的对比可以这样看方法时间复杂度空间复杂度代码量推荐程度暴力双重循环O(N^2)O(1)很少不推荐哈希表统计出度O(N)O(N)中等可选哈希集合找不在起点中的终点O(N)O(N)最少强烈推荐你可能会问出度统计和哈希集合法看起来差不多为什么要选后者原因在于哈希集合法省去了“计数”这个中间状态。统计出度要维护每个城市的出现次数如果你只需要找“最后剩下的那个节点”用集合天然去重的特性反而更贴合题意。而且集合版的代码短写起来不容易出错在周赛的环境下代码越短出bug的概率越低。3. 多语言实现把思路写成不会出错的代码3.1 Python实现与细节Python 的代码可以写得非常紧凑。先把所有起点收集到一个集合里再找不在集合中的终点class Solution: def destCity(self, paths: List[List[str]]) - str: starts set() for path in paths: starts.add(path[0]) for path in paths: if path[1] not in starts: return path[1]如果你喜欢更 Pythonic 的风格也可以用集合推导式和 next 表达式一行搞定核心逻辑class Solution: def destCity(self, paths: List[List[str]]) - str: starts {path[0] for path in paths} return next(path[1] for path in paths if path[1] not in starts)这里面有几个值得注意的细节。第一Python 的 set 是无序且去重的你不需要担心里面出现重复的起点。第二next 函数在生成器找不到元素时会抛出 StopIteration 异常但题目保证一定存在唯一的终点站所以这里不会触发。第三如果你用的是 Python 老版本List 的 typing 注解要记得从 typing 模块导入但在现代 LeetCode 环境里直接用 list 也可以。我看到有些人会图省事直接统计所有城市出现的次数返回出现次数为1的城市。这个写法在大部分测试用例上都能过但它是错的后面我会专门讲这个坑。3.2 C和Java写法示例C 的思路完全一样用 unordered_set 存起点class Solution { public: string destCity(vectorvectorstring paths) { unordered_setstring starts; for (auto p : paths) { starts.insert(p[0]); } for (auto p : paths) { if (starts.find(p[1]) starts.end()) { return p[1]; } } return ; } };Java 的写法则要稍微注意一下泛型和 List 的取值方式class Solution { public String destCity(ListListString paths) { SetString starts new HashSet(); for (ListString p : paths) { starts.add(p.get(0)); } for (ListString p : paths) { if (!starts.contains(p.get(1))) { return p.get(1); } } return ; } }C 里 unordered_set 的 find 和 end 比较是标准操作要注意别把 insert 后的返回值弄混了。Java 里 HashSet 的 contains 方法时间复杂度是 O(1)所以整体思路和 Python 版完全一致。三个语言用的是同一套逻辑这就说明你真正需要掌握的是“把起点放入集合再从终点里找答案”这个模型而不是死记某一种语言的语法。3.3 边界条件和代码健壮性写完之后建议自己在脑子里跑两个极端情况。第一个是 paths 只有一条路线比如 [[A,B]]这时起点集合是 {A}终点 B 不在集合中直接返回 B没有任何问题。第二个是所有城市组成一条长链比如 [[A,B],[B,C],[C,D]]起点集合是 {A,B,C}终点集合是 {B,C,D}只有 D 不在起点集合里正确。还有一个小问题如果 paths 里出现了空数组怎么办题目描述中 paths[i] 是长度为2的数组但数据范围那里写的 0 paths[i].length 100 会让一些人多虑。在实际测试用例中paths[i] 一定是合法的一对城市名不需要额外判空。不过你要是想写得特别稳也可以在遍历时加上长度判断但这属于防御性编程周赛里不建议花这个时间。4. 实战复盘周赛里这道题最容易踩的坑4.1 常见错误与反例这道题最大的坑就是“统计所有城市出现次数返回只出现一次的城市”。很多新手会踩进去我当初第一次做这题也差点这么干。给你一个反例就明白了paths [[A,B],[C,A],[D,C]]这条线路是 D-C-A-B终点是 B。现在统计所有城市出现次数A 出现2次C 出现2次D 出现1次B 出现1次。如果按照“只出现一次”来判定D 和 B 都是候选答案但 D 是起点根本不是终点站。所以只看出现次数完全不靠谱必须区分一个城市是“作为起点出现”还是“作为终点出现”。另一个容易犯的错误是把思路搞反去找“不在任何终点里的起点”也就是想找起点站。注意题目问的是终点站不是起点站。虽然这两个问题对称但一不留神就会写反。找起点的做法是把所有终点放进集合然后返回不在集合中的起点。这道题的正确答案是反过来把所有起点放进集合返回不在集合中的终点。我见过有群友赛后复盘说自己的代码逻辑看起来完全没问题结果一提交就 WA仔细一看就是把 start 和 dest 的集合搞反了。4.2 周赛抢分策略周赛的 T1 通常是最简单的题目目标是在极短时间内 AC。根据我的经验这题的理想时间线是这样的读题30秒建模30秒写代码30秒跑示例验证20秒总用时控制在2分钟以内。如果你在 T1 上花了超过5分钟说明你需要加强“把文字描述翻译成数据结构”的练习。很多人一看到图论、路线、城市这些词就开始脑补复杂的DFS或拓扑排序。实际上你只要瞄一眼数据范围——paths 长度最多100——就该知道 T1 考的不是算法复杂度而是基本建模能力。在 T1 上使用 DFS 或者建邻接表属于典型的杀鸡用牛刀。不是说不行而是你花了更多时间写复杂代码反而增加了出错的概率。我的建议是周赛开始后先把四道题都扫一眼T1 直接按“哈希集合”套路秒掉把节约下来的时间留给后面的 T2 和 T3。因为周赛排名很大程度上取决于完成时间T1 的 AC 时间每慢一分钟排名都会往后掉一大截。4.3 快速自查清单做完这道题之后我会在提交前默念几个检查点是否把所有起点都加入了集合有没有漏掉最后一条路径返回的是终点而不是起点判断条件是不是path[1] not in starts如果 paths 长度为1代码能否正常返回唯一终点如果存在 A-B 和 B-A 这样的循环结果会怎样这个输入违反了题目“唯一终点”的约束所以不需要额外处理但你可以想想自己的代码在这种情况下会返回什么有助于加深理解。这个自查过程只需要10秒但对避免低级失误非常有效。特别是第四条我建议你多想想它不违反题意但能帮你理解出度和入度的关系。5. 从这道题延伸出去的图论思维5.1 入度出度模型在其他题目中的应用做完这道题如果只是记住“用set找终点”那就太可惜了。这道题背后藏着的是图论里非常基础也非常重要的入度出度模型。所谓入度就是有多少条边指向这个节点出度就是有多少条边从这个节点指出。很多看起来完全不同的题目最后都能归结为找入度或出度满足特定条件的节点。LeetCode 里非常出名的一道题——找小镇法官就是同一个模型。题目描述是小镇里有 N 个人法官不相信任何人所有人都信任法官。翻译成图论语言就是法官的入度是 N-1出度是0。你需要找到那个唯一同时满足这两个条件的节点。你看这和本道题“终点站入度至少1、出度为0”的判定方式何其相似。再比如拓扑排序中找入度为0的节点作为起点本质上也是在玩入度出度这套东西。所以当你把“旅行终点站”这道题吃透再去刷其它图论入门题你会发现自己能很快地辨认出题目背后的核心考点而不是被表面的故事包装迷惑。5.2 面试和工程中怎么迁移这套思路面试的时候这道题可以有很多变体。比如给你一份任务依赖列表每个任务依赖另一个任务让你找出最后的那个任务或者给你一组“先修课程”的二元组让你判断学习顺序。这些题目的本质都是图上的入度出度分析。工程上也有类似的场景。我实际开发中遇到过这样一个需求有一组服务调用链记录每条记录是 [调用方, 被调用方]需要找出整个调用链最末端那个服务。这不就是旅行终点站的翻版吗只不过把城市名换成了服务名把旅行线路换成了调用关系。这时候哈希集合的解法可以直接迁移过来连算法都不用改。所以我觉得做算法题的最高境界不是背题而是建立“题目特征到算法模型”的映射。看到“给一堆二元组找唯一特殊节点”脑子里立刻跳出“集合差值入度出度哈希表”这几个关键词那你刷这道题的时间就没有白费。这题给我最大的启发是简单题里往往藏着最常用的图论思维。不要因为 AC 了就急着做下一题停下来想一想为什么哈希集合能一步定位终点想一想如果路径再多100倍这题还能不能这么写。把这些想明白下次遇到 T1你就能做到看到题目的那一刻已经知道代码要怎么写了。
