介紹

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

適合人群：

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

不適合人群：

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

非常不適合人群：

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

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

巴士路線

題目看這里，leetcode第815題，hard難度：
https://leetcode.com/problems/bus-routes/description/

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

解析

這道題其實(shí)很獨(dú)特，通常我們做bfs都是以節(jié)點(diǎn)為單位進(jìn)行擴(kuò)展，但在這道題目中，我們需要根據(jù)公交路線（或稱(chēng)為“路由”）進(jìn)行擴(kuò)展。這意味著，當(dāng)我們從一個(gè)站點(diǎn)開(kāi)始搜索時(shí)，我們不是僅僅訪問(wèn)鄰近的站點(diǎn)，而是訪問(wèn)該站點(diǎn)上所有公交線路所到達(dá)的所有站點(diǎn)。換句話(huà)說(shuō)，當(dāng)我們“乘坐”一輛公交車(chē)時(shí)，我們可以視為幾乎“立即”訪問(wèn)了該線路上的所有站點(diǎn)。（以上為ChatGPT的觀點(diǎn)，我覺(jué)得說(shuō)得很清楚）

思考樂(lè)園

如果一個(gè)車(chē)站被兩條或多條公交路線共同經(jīng)過(guò)，以上程序?qū)⑷绾翁幚磉@種情境？歡迎將答案寫(xiě)在評(píng)論區(qū)～

音樂(lè)推薦

筆者昨天做這題時(shí)總想著每次遍歷一個(gè)車(chē)站，于是就順利卡住，未能及時(shí)發(fā)專(zhuān)欄。到最后還是在床上干躺著的時(shí)候忽然發(fā)現(xiàn)其中玄機(jī)，原來(lái)每一步是指當(dāng)前不換乘車(chē)所能到達(dá)的所有車(chē)站。此題本身實(shí)現(xiàn)不難，但是這個(gè)思考角度確實(shí)非常有趣。這首來(lái)自法里達(dá)的逍遙一客送給終于到達(dá)周末的你。博得之門(mén)3，啟動(dòng)！

教材鏈接

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