【LeetCode通关全记录】1436. 旅行终点站

题目地址👉 1436. 旅行终点站

解法1：结点-出度表（想复杂了）

看到这题第一反应是图，题目中要求的又是出度为0的结点，那么自然而然地就想到了求所有结点的出度并保存在map中，最后遍历map并返回出度为0的结点的方法。

详细解法请看注释👇

func destCity(paths [][]string) string {
  // path数组的第一个参数为起点,第二个参数为终点
    // 那么我们就可以建立一个map,key为城市(结点),value为从该城市出发的线路条数(出度)
    // 遍历二维数组中的每一条路线
    // 若起点不在map中,则把起点放入map并置出度为1
    // 若终点不在map中,则把终点放入map并置出度为0
    // 若起点在map中,则把对应起点的出度加1
    // 若终点在map中,则不做任何处理
    // 最后返回出度为0的结点名称即可
    if len(paths) == 0 {
        return ""
    }
    g := make(map[string]int, 0)
    for _, city := range paths {
        if _, ok := g[city[0]]; !ok {
            // 若起点不在map中,则把起点放入map并置出度为1
            g[city[0]] = 1
        } else {
            // 若起点在map中,则把对应起点的出度加1
            g[city[0]] += 1
        }
        // 若终点不在map中,则把终点放入map并置出度为0
        if _, ok := g[city[1]]; !ok {
            g[city[1]] = 0
        }
    }
    for k, v := range g {
        // 最后返回出度为0的结点名称即可
        if v == 0 {
            return k
        }
    }
    return ""
}

执行用时: 4 ms（超过85%的Golang提交记录）

内存消耗: 4 MB（超过31%的Golang提交记录）

时间复杂度：O(n)

空间复杂度：O(n)

解法2：哈希表的正确使用方法（官方解法）

我本来以为我想到的解法是一个比较正常的解法，但是看了官方题解之后我发现我想的实在是太复杂了，果然感冒的时候就应该好好休息不要刷题。。。

官方解法的思路其实很简单：因为一条线路的起点站是path[0]，终点站是path[1]，所以在path[1]中出现而没有在path[0]中出现的结点就是我们要求的终点站了。

func destCity(paths [][]string) string {
  // 官方解法,建哈希表,比我自己想的要简单
    if len(paths) == 0 {
        return ""
    }
    s := make(map[string]bool, 0)
    for _, route := range paths {
        s[route[0]] = true
    }
    for _, route := range paths {
        if _, ok := s[route[1]]; !ok {
            return route[1]
        }
    }
    return ""
}

执行用时: 4 ms（超过85%的Golang提交记录）

内存消耗: 3.9 MB（超过64%的Golang提交记录）

时间复杂度：O(n)

空间复杂度：O(n)