【LeetCode通關全記錄】1436. 旅行終點站
題目地址?? 1436. 旅行終點站
解法1：結點-出度表（想復雜了）
看到這題第一反應是圖，題目中要求的又是出度為0的結點碱屁，那么自然而然地就想到了求所有結點的出度并保存在map中，最后遍歷map并返回出度為0的結點的方法。
詳細解法請看注釋??
func destCity(paths [][]string) string {
// path數(shù)組的第一個參數(shù)為起點,第二個參數(shù)為終點
// 那么我們就可以建立一個map,key為城市(結點),value為從該城市出發(fā)的線路條數(shù)(出度)
// 遍歷二維數(shù)組中的每一條路線
// 若起點不在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 ""
}
執(zhí)行用時: 4 ms（超過85%的Golang提交記錄）
內存消耗: 4 MB（超過31%的Golang提交記錄）
時間復雜度：O(n)
空間復雜度：O(n)
解法2：哈希表的正確使用方法（官方解法）
我本來以為我想到的解法是一個比較正常的解法误堡，但是看了官方題解之后我發(fā)現(xiàn)我想的實在是太復雜了赠橙，果然感冒的時候就應該好好休息不要刷題婶希。。蛆封。
官方解法的思路其實很簡單：因為一條線路的起點站是path[0]，終點站是path[1]勾栗，所以在path[1]中出現(xiàn)而沒有在path[0]中出現(xiàn)的結點就是我們要求的終點站了惨篱。
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 ""
}
執(zhí)行用時: 4 ms（超過85%的Golang提交記錄）
內存消耗: 3.9 MB（超過64%的Golang提交記錄）
時間復雜度：O(n)
空間復雜度：O(n)
