题目链接

题目

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

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

示例 1：

  1. 输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
  2. 输出："Sao Paulo" 
  3. 解释：从 "London" 出发，最后抵达终点站 "Sao Paulo" 
  4.      本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。

示例 2：

  1. 输入：paths = [["B","C"],["D","B"],["C","A"]]
  2. 输出："A"
  3. 解释：所有可能的线路是：
  4. "D" -> "B" -> "C" -> "A". 
  5. "B" -> "C" -> "A". 
  6. "C" -> "A". 
  7. "A". 
  8. 显然，旅行终点站是 "A" 。

示例 3：

  1. 输入：paths = [["A","Z"]]
  2. 输出："Z"

提示：

  • 1 <= paths.length <= 100
  • paths[i].length == 2
  • 1 <= cityAi.length, cityBi.length <= 10
  • cityAi != cityBi
  • 所有字符串均由大小写英文字母和空格字符组成。

解题思路

只要没当过起点的终点，一定是最终终点，所以可以建立 “起点集合” 和“终点集合”，两者相减，终点集合剩下的就是最终终点

代码实现 1

这个是自己写的代码，解题思路是对的，但是实际操作的时候会把操作想复杂。。。

  1.     public String destCity(List<List<String>> paths) {
  2.         // 构建 出发集合 和 终点集合
  3.         Set<String> startSet = new HashSet<>();
  4.         Set<String> endSet = new HashSet<>();
  6.         paths.forEach(path -> {
  7.             startSet.add(path.get(0));
  8.             endSet.add(path.get(1));
  9.         });
  10.         endSet.removeAll(startSet);
  11.         String rs = null;
  12.         for (String s : endSet) {
  13.             rs = s;
  14.         }
  15.         return rs;
  16.     }

执行结果：
image.png

代码实现 2

    public static String destCity(List<List<String>> paths) {
        Set<String> citiesA = new HashSet<String>();
        // 获取所有的出发集
        for (List<String> list : paths) {
            map.put(list.get(0), 1);
        }
        for (List<String> path : paths) {
            // 从终点集中找到出发集，如果没有找到，就是最终目的地
            if (!citiesA.contains(path.get(1))) {
                return path.get(1);
            }
        }       
        return "";
    }

执行结果：
image.png