题目地址：https://leetcode-cn.com/problems/destination-city/
题目描述
给你一份旅游线路图，该线路图中的旅行线路用数组 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、 1<=paths.length<=100；
2、 paths[i].length==2；
3、 1<=cityAi.length,cityBi.length<=10；
4、 cityAi!=cityBi；
5、 所有字符串均由大小写英文字母和空格字符组成；
题目大意
给出的是一个有向无环图，找出旅行的终点站。
解题方法
set
第一个感觉是 拓扑排序，但这个是周赛的 Easy 题，应该很简单。
注意题目给出的条件：只会有一个旅行终点站。
所以，我们找出 哪个站 没有出度就行了。说人话：只有一个站不会出现在出发点上。
所以，对所有的站进行统计，如果一个站没有出现在出发点上，那这个站就是最终的旅行终点站。
Python 代码如下：
class Solution(object):
def destCity(self, paths):
"""
:type paths: List[List[str]]
:rtype: str
"""
starts = set()
ends = set()
for path in paths:
starts.add(path[0])
ends.add(path[1])
for end in ends:
if end not in starts:
return end
return ""
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发