【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)
