跳至主要內容

1436. 旅行终点站

1436. 旅行终点站

🟢   🔖  数组 哈希表 字符串  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi. Return the destination city, that is, the city without any path outgoing to another city.

It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.

Example 1:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]

Output: "Sao Paulo"

Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

Example 2:

Input: paths = [["B","C"],["D","B"],["C","A"]]

Output: "A"

Explanation: All possible trips are:

"D" -> "B" -> "C" -> "A".

"B" -> "C" -> "A".

"C" -> "A".

"A".

Clearly the destination city is "A".

Example 3:

Input: paths = [["A","Z"]]

Output: "Z"

Constraints:

  • 1 <= paths.length <= 100
  • paths[i].length == 2
  • 1 <= cityAi.length, cityBi.length <= 10
  • cityAi != cityBi
  • All strings consist of lowercase and uppercase English letters and the space character.

题目大意

给你一份旅游线路图，该线路图中的旅行线路用数组 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. 使用一个 Set 来存储所有路径的起点城市。

    • 遍历 paths 数组，将每条路径的起点城市加入 Set。

  2. 再次遍历 paths，检查每条路径的终点城市是否不在 Set 中。

    • 旅行的终点站，是没有任何可以通往其他城市的线路的城市。
    • 所以，如果某个终点城市不在 Set 中，说明它是旅行的终点站，直接返回。

  3. 如果遍历结束仍未找到，返回空字符串（理论上题目保证有解，不会到达这一步）。

复杂度分析

  • 时间复杂度: O(n)，其中 n 是 paths 的长度，遍历 paths 两次。
  • 空间复杂度: O(n)，使用 Set 存储起点城市，最坏情况下有 n 个起点城市。

代码

/**
 * @param {string[][]} paths
 * @return {string}
 */
var destCity = function (paths) {
	let outgoing = new Set();
	for (let [a, b] of paths) {
		outgoing.add(a);
	}
	for (let [a, b] of paths) {
		if (!outgoing.has(b)) {
			return b;
		}
	}
	return '';
};
Copyright © 2024 2xiao