力扣（leetcode）每日一题 1436 旅行终点站

1436. 旅行终点站

题干

给你一份旅游线路图，该线路图中的旅行线路用数组 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"

题解

public static String destCity(List<List<String>> paths) {  
    HashMap<String, String> map = new HashMap<>();  
    // start  
    String start = paths.get(0).get(1); // a-b  a是起始点，然后a跳到b后，start起使点就是b  
    for (List<String> path : paths) {  
        if (start.equals(path.get(0))) {  // 如果这里是b到c，就直接更新c。   也就是b到c，start起始点为c。这里的点也不需要再放入map中。 这里的机制可以加速跳转  
            start = path.get(1);  
        } else {  
            map.put(path.get(0), path.get(1));  
        }  
    }  
    while (map.get(start) != null) {  // 通过map进行点的跳转
        start = map.get(start);  
    }  
    return start;  
}

总结

这里需要知道，这个就是一个点到点的跳转。不是要从开始点跳转。任意一点都可以跳转到终点，而舍弃之前的点。