企业官网建设流程全解析

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 复杂度与适用场景对比

三种方法的对比可以这样看：

你可能会问，出度统计和哈希集合法看起来差不多，为什么要选后者？原因在于哈希集合法省去了“计数”这个中间状态。统计出度要维护每个城市的出现次数，如果你只需要找“最后剩下的那个节点”，用集合天然去重的特性反而更贴合题意。而且集合版的代码短，写起来不容易出错，在周赛的环境下，代码越短，出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(vector<vector<string>>& paths) { unordered_set<string> 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(List<List<String>> paths) { Set<String> starts = new HashSet<>(); for (List<String> p : paths) { starts.add(p.get(0)); } for (List<String> 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，你就能做到看到题目的那一刻，已经知道代码要怎么写了。