Easy

题目描述

给你一个数组 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 <= paths.length <= 100
  • paths[i].length == 2
  • 1 <= cityAi.length, cityBi.length <= 10
  • cityAi != cityBi
  • 所有字符串都由大小写英文字母和空格字符组成。

解题思路

解题思路

这道题的核心思想是找到没有出度的城市，即只作为目的地出现，从不作为起点的城市。

方法一：哈希集合求差集

  1. 创建两个集合：一个存储所有起点城市，一个存储所有终点城市
  2. 终点城市集合中去除起点城市集合，剩下的唯一城市就是答案
  3. 时间复杂度O(n)，空间复杂度O(n)

方法二：哈希表统计出度

  1. 遍历所有路径，统计每个城市的出度（作为起点的次数）
  2. 找到出度为0的城市，即为终点站
  3. 时间复杂度O(n)，空间复杂度O(n)

方法三：直接查找（推荐）

  1. 将所有起点城市放入集合中
  2. 遍历所有终点城市，找到第一个不在起点集合中的城市
  3. 这种方法最直观，代码简洁

推荐使用方法三，因为它逻辑最清晰，代码最简洁。

代码实现

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        unordered_set<string> startCities;
        
        // 收集所有起点城市
        for (const auto& path : paths) {
            startCities.insert(path[0]);
        }
        
        // 找到不是起点的终点城市
        for (const auto& path : paths) {
            if (startCities.find(path[1]) == startCities.end()) {
                return path[1];
            }
        }
        
        return "";
    }
};

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        start_cities = set()
        
        # 收集所有起点城市
        for path in paths:
            start_cities.add(path[0])
        
        # 找到不是起点的终点城市
        for path in paths:
            if path[1] not in start_cities:
                return path[1]
        
        return ""

public class Solution {
    public string DestCity(IList<IList<string>> paths) {
        HashSet<string> startCities = new HashSet<string>();
        
        // 收集所有起点城市
        foreach (var path in paths) {
            startCities.Add(path[0]);
        }
        
        // 找到不是起点的终点城市
        foreach (var path in paths) {
            if (!startCities.Contains(path[1])) {
                return path[1];
            }
        }
        
        return "";
    }
}

var destCity = function(paths) {
    const startCities = new Set();
    
    // 收集所有起点城市
    for (const path of paths) {
        startCities.add(path[0]);
    }
    
    // 找到不是起点的终点城市
    for (const path of paths) {
        if (!startCities.has(path[1])) {
            return path[1];
        }
    }
    
    return "";
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(n)

其中 n 是路径数组的长度。我们需要遍历两次数组，第一次收集起点城市，第二次查找终点城市，每次操作都是O(1)的哈希操作。空间复杂度主要来自存储起点城市的哈希集合。