介紹

總而言之是時(shí)候利用暑假鍛煉一下算法技術(shù)，一提算法面試就面露難色的情形總不能一直持續(xù)下去。本欄目面向有一定基礎(chǔ)的編程愛(ài)好者，每天（如果up不鴿）分享并解析一道LeetCode中高難度題目（通常是hard）。有興趣的小伙伴可以一起跟著做并且討論解法。目前的教材是花花醬的Leetcode Problem List【1】.

適合人群：

有一定算法基礎(chǔ)，但是還未能順利通過(guò)筆試/面試，總覺(jué)得算法題目想不明白的你。

不適合人群：

算法入門(mén)級(jí)選手（一上來(lái)就做難題可能并不合適，建議首先專注簡(jiǎn)單/中等題目）

非常不適合人群：

算法競(jìng)賽選手（這種小兒科的問(wèn)題完全是在浪費(fèi)您的時(shí)間）

過(guò)往題目在這里！

網(wǎng)絡(luò)延遲時(shí)間

題目看這里，lintcode第1057題，medium難度：
https://www.lintcode.com/problem/1057/

強(qiáng)烈建議讀者自己先做（不過(guò)真的會(huì)有讀者嗎，笑），有任何問(wèn)題歡迎在評(píng)論區(qū)討論，up看到了會(huì)及時(shí)回復(fù)。做完了歡迎在評(píng)論區(qū)打卡～

解析

雖然看起來(lái)是圖遍歷的簡(jiǎn)單題目，要注意每條邊的經(jīng)過(guò)時(shí)間都是不同的。這里我們用了經(jīng)典的SPFA（Shortest Path Faster Algorithm）算法。基本上就是，如果到某個(gè)節(jié)點(diǎn)的時(shí)間比記錄的短，那就再更新一次。

思考樂(lè)園

在第二個(gè)while循環(huán)里，我們用visited[cur_node]獲取了到當(dāng)前節(jié)點(diǎn)的時(shí)間。這里我為什么不擔(dān)心cur_node會(huì)不在visited中？歡迎把答案寫(xiě)到評(píng)論區(qū)～

音樂(lè)推薦

今天去剪頭發(fā)，但是坐了半天公交車之后發(fā)現(xiàn)理發(fā)店并沒(méi)有開(kāi)門(mén)，最后還是自己剪的，甚至還有點(diǎn)不錯(cuò)。這首來(lái)自法里達(dá)的帶我去找夜生活送給心境平和的你。

教材鏈接

【1】https://zxi.mytechroad.com/blog/leetcode-problem-categories/