1436. 旅行终点站

Posted on Edited on In , ,
转载自Leet Code

题目描述

给定一份旅游线路图，其中的旅行线路用数组paths表示，

其中paths[i] = [cityAi, cityBi]表示该线路将会从cityAi直达cityBi。

请找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。

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

示例1:

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

输出: "Sao Paulo"

示例2:

输入: paths = [["B","C"],["D","B"],["C","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
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class MySolution1436 {
    public String destCity(List<List<String>> paths) {
    	HashSet<String> set = new HashSet(); // HashMap->Set
    	HashSet<String> ans = new HashSet();
    	for (int i=0; i<paths.size(); i++)
    	{
    		String key = paths.get(i).get(0);
    		set.add(key);
    		if (ans.contains(key)) ans.remove(key); 
    		
    		String val = paths.get(i).get(1);
    		if (!set.contains(val)) {
    			ans.add(val);
    			set.add(val);
    		}
    	}
    	return ans.iterator().next();
    }
}

方法：哈希表

根据定义，终点站不可能出现在cityAi中，而必然出现在cityBi中。

因此可以遍历cityBi、返回不在cityAi中的城市。

实现: 先把所有cityAi 存在哈希表中，然后遍历cityBi并查询cityBi是否存在于哈希表中。

代码

\(T(N) = O(MN), S(N) = O(MN); (N: 数组paths的长度; M: 最长的paths[i]的长度)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution1436 {
    public String destCity(List<List<String>> paths) {
    	String str = "";
    	HashSet<String> set = new HashSet();
    	for (List<String> list:paths)
    		set.add(list.get(0));
    	for (List<String> list:paths) {
    		if (!set.contains(list.get(1))) {
    			str = list.get(1); break;
			}
    	}
    	return str;
    }
}