【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 ""
}