旅行终点站

难度: Easy

给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityA_i, cityB_i] 表示该线路将会从 cityA_i 直接前往 cityB_i 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。

题目数据保证线路图会形成一条不存在循环的线路，因此恰有一个旅行终点站。

示例 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 <= paths.length <= 100
paths[i].length == 2
1 <= cityA_i.length, cityB_i.length <= 10
cityA_i!= cityB_i
所有字符串均由大小写英文字母和空格字符组成。

Submission

运行时间: 18 ms

内存: 16.1 MB

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        start_set=set()
        finish_set=set()
        for start,finish in paths:
            start_set.add(start)
            finish_set.add(finish)
        return list(finish_set-start_set)[0]

Explain

题解的思路是通过使用两个集合来区分起始城市和目的地城市。对于每一条路径，将起点城市添加到起始集合，将终点城市添加到终点集合。由于每个城市只有一条出发路线，终点站将不会出现在起始集合中。因此，通过计算终点集合与起始集合的差集，即可得到终点站。由于题目保证了路径的连续性且无环，这个差集中将只有一个元素，即为我们需要的终点站。

时间复杂度: O(n)

空间复杂度: O(n)

# 类定义

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        start_set = set()  # 存储所有起点城市
        finish_set = set()  # 存储所有终点城市
        for start, finish in paths:  # 遍历所有路径
            start_set.add(start)  # 将起点城市添加到起点集合
            finish_set.add(finish)  # 将终点城市添加到终点集合
        # 计算终点集合和起点集合的差集，取第一个元素作为结果
        return list(finish_set - start_set)[0]

Explore

是的，题解中使用的方法可以有效处理所有情况，包括连续多个路径有相同的起始或终点城市的情况。由于集合只存储唯一元素，即使多条路径的起点或终点相同，也只会在集合中保留一个该城市的记录。因此，这种方法可以准确地通过集合运算找出唯一的终点城市，这是因为终点城市将不会出现在任何路径的起点中。

题解中选择使用集合而不是列表或字典主要是因为集合提供了快速的成员检查和独特性保证。集合自动处理重复元素，确保每个元素只出现一次，这在检查路径起点和终点是否重复时非常有用。此外，集合提供了方便的集合操作方法，如差集，这可以直接用来找到不在起点集合中的终点，这种操作如果使用列表或字典实现，则会更加复杂和耗时。

根据题目的设定，每个城市只有一条出发路线，确保了路径的连续性且无环，因此在正常情况下，终点集合与起点集合的差集中应只有一个元素，即最终的终点站。如果存在多个不在起始集合中的城市，则这可能表明输入数据不符合题目的假设条件。在这种情况下，题解的逻辑需要重新审视，或需要更多信息来正确处理异常情况。

是的，这一行代码有潜在的风险。如果差集为空，即`finish_set - start_set`结果为空集，那么将其转换为列表后访问第一个元素`[0]`会引发`IndexError`异常，因为列表中没有任何元素。在实际应用中，应该先检查差集是否为空，以避免运行时错误。可以通过添加适当的错误处理或条件检查来增强代码的健壮性。