陜西富通建設(shè)工程有限公司網(wǎng)站,順德醫(yī)療網(wǎng)站建設(shè),咋做網(wǎng)站,html電影網(wǎng)站源碼這是一個(gè)非常核心的問題。#xff1a;DFS#xff08;深度優(yōu)先搜索#xff09;首先是一種思想#xff0c;然后才是具體題目中的代碼實(shí)現(xiàn)。 理解 DFS 的關(guān)鍵在于#xff1a;“不撞南墻不回頭”。1. DFS 的本質(zhì)思想 DFS 的核心邏輯是#xff1a;從一個(gè)起點(diǎn)出發(fā)#xff0c;選…這是一個(gè)非常核心的問題。DFS深度優(yōu)先搜索首先是一種思想然后才是具體題目中的代碼實(shí)現(xiàn)。理解 DFS 的關(guān)鍵在于“不撞南墻不回頭”。1. DFS 的本質(zhì)思想DFS 的核心邏輯是從一個(gè)起點(diǎn)出發(fā)選定一個(gè)方向死磕到底直到走不通了撞到邊界、遇到水、或者已經(jīng)訪問過再退回上一步換個(gè)方向繼續(xù)死磕。二叉樹中是一路向下扎到葉子節(jié)點(diǎn)。網(wǎng)格島嶼中是一路向上下左右某一個(gè)方向走到底。這種“回退”的動作在代碼里通過“遞歸”或“棧”來實(shí)現(xiàn)。2. DFS 的通用“三部曲”模板無論什么題目DFS 的代碼結(jié)構(gòu)幾乎都是固定的邊界判定Base Case我是不是出界了我是不是已經(jīng)來過這了防止死循環(huán)標(biāo)記訪問Marking既然我來了就給這里打個(gè)標(biāo)記免得一會兒又繞回來。遞歸搜索Recursion往所有可能的方向繼續(xù)走。3. 為什么《島嶼數(shù)量》的操作就是 DFSimportsys# 設(shè)置遞歸深度限制防止大矩陣導(dǎo)致棧溢出sys.setrecursionlimit(200000)defsolve():# 1. 處理輸入 (ACM 模式常見寫法)input_datasys.stdin.read().split()ifnotinput_data:return# 獲取行數(shù)和列數(shù)rowsint(input_data[0])colsint(input_data[1])# 將剩余的一維數(shù)據(jù)填充進(jìn)二維網(wǎng)格 grid[rows][cols]grid[]foriinrange(rows):# 每一行取 cols 個(gè)元素start2i*cols grid.append(list(input_data[start:startcols]))# 2. 定義 DFS 沉島函數(shù)defdfs(r,c):# 邊界條件坐標(biāo)越界 或 遇到水(0) 則返回ifr0orrrowsorc0orccolsorgrid[r][c]0:return# 沉島操作將當(dāng)前陸地標(biāo)記為 0防止重復(fù)訪問grid[r][c]0# 遞歸訪問上下左右四個(gè)方向dfs(r-1,c)# 上dfs(r1,c)# 下dfs(r,c-1)# 左dfs(r,c1)# 右# 3. 遍歷網(wǎng)格尋找島嶼island_count0forrinrange(rows):forcinrange(cols):# 只要發(fā)現(xiàn)一塊陸地就是一個(gè)新島嶼的開始ifgrid[r][c]1:island_count1# 使用 DFS 把它連通的所有陸地全部“淹沒”dfs(r,c)# 4. 輸出結(jié)果print(island_count)if__name____main__:solve()對比上面的模板你看《島嶼數(shù)量》的代碼邏輯起點(diǎn)遍歷整個(gè)網(wǎng)格遇到1陸地就開工。死磕到底dfs(r1, c)、dfs(r-1, c)… 這就是在往四個(gè)方向死磕。撞墻回頭遇到邊界或0水就return。標(biāo)記把1變成0。索引是從 0 開始的0-indexed。在編程中這是一個(gè)非常經(jīng)典且容易出錯(cuò)的“差一錯(cuò)誤”O(jiān)ff-by-one error。我們可以通過一個(gè)小例子看明白1. 為什么r rows必須攔截假設(shè)你的網(wǎng)格有3 行即rows 3第 1 行的索引是0第 2 行的索引是1第 3 行的索引是2最大的合法索引是rows - 1也就是 2。如果你此時(shí)代碼里的r等于3即r rows你去訪問grid[3]程序會立刻報(bào)錯(cuò)IndexError: list index out of range。因?yàn)榈?4 行索引為 3 的行根本不存在。2. 這個(gè)條件的邏輯拆解這一行判定條件其實(shí)是給遞歸設(shè)定的**“安全護(hù)欄”**ifr0orrrowsorc0orccolsorgrid[r][c]0:r 0: 往“上”走過頭了出了天花板。r rows: 往“下”走過頭了出了地板。c 0: 往“左”走過頭了出了左墻壁。c cols: 往“右”走過頭了出了右墻壁。grid[r][c] 0: 沒出界但踩到水了不需要處理。只有避開了以上所有“雷區(qū)”我們才能安全地執(zhí)行g(shù)rid[r][c]的操作。3. 一個(gè)幫你記住的口訣在處理矩陣題目時(shí)你可以記住這個(gè)**“合法區(qū)間”**索引的范圍是 。只要“等于”或“超過”了長度就是非法。 進(jìn)階小技巧為什么順序很重要在這一行代碼中條件的順序其實(shí)救了程序的命# 正確順序先判斷邊界再訪問數(shù)組ifr0orrrowsor...orgrid[r][c]0:Python 在執(zhí)行or時(shí)有**“短路邏輯”**如果r rows成立比如3 3為真Python 會認(rèn)為整個(gè)if已經(jīng)成立了。它不會再去執(zhí)行后面的grid[r][c] 0。這樣就巧妙地避免了在索引越界時(shí)去訪問數(shù)組導(dǎo)致的崩潰。如果你把順序反過來寫if grid[r][c] 0 or r rows ...程序會先嘗試訪問grid[3][c]然后直接報(bào)錯(cuò)死掉根本沒機(jī)會運(yùn)行到后面的邊界檢查。為什么這叫 DFS因?yàn)樗鼤劝涯骋粋€(gè)方向相連的所有陸地全部摸透然后再返回去摸另一條分支。這完美符合“深度優(yōu)先”的定義。4. 具體情況具體分析不同結(jié)構(gòu)的 DFS雖然思想統(tǒng)一但針對不同數(shù)據(jù)結(jié)構(gòu)DFS 的“方向”和“標(biāo)記”方式不同A. 二叉樹的 DFS方向只有兩個(gè)左孩子、右孩子。標(biāo)記通常不需要手動標(biāo)記因?yàn)闃涞慕Y(jié)構(gòu)是向下的不會往回走。代碼dfs(node.left)dfs(node.right)。B. 二維數(shù)組網(wǎng)格/島嶼的 DFS方向四個(gè)或八個(gè)上下左右有時(shí)加斜向。標(biāo)記必須標(biāo)記沉島或visited數(shù)組因?yàn)榫W(wǎng)格是連通的不標(biāo)記會死循環(huán)。代碼dfs(r1, c)、dfs(r, c1)等。C. 排列組合題的 DFS回溯方向數(shù)組中還沒用過的數(shù)字。標(biāo)記used[i] True遞歸used[i] False回溯的關(guān)鍵撤銷標(biāo)記。區(qū)別島嶼題不需要撤銷標(biāo)記沉了就沉了但排列題需要撤銷為了嘗試下一種排列。5. 總結(jié)DFS 的通用細(xì)節(jié)表維度二叉樹 DFS網(wǎng)格島嶼 DFS全排列 DFS (回溯)終止條件if not nodeif 越界 or grid[i][j]0if 路徑長度 目標(biāo)長度訪問標(biāo)記無需通常沉島將 1 改為 0used 數(shù)組擴(kuò)散方式left/right上下左右for i in range(len(nums))是否回溯否否是必須恢復(fù)現(xiàn)場 備考建議你在面試中如果聽到“連通性”、“所有路徑”、“尋找所有可能的組合”腦子里第一反應(yīng)就應(yīng)該是DFS。《單詞搜索 (LeetCode 79)》。這題也是網(wǎng)格但它比島嶼數(shù)量多了一個(gè)**“回溯”的動作因?yàn)槁纷卟煌ㄒ嘶貋戆褬?biāo)記還原。這道題是DFS 回溯 (Backtracking)的教科書級案例。它和《島嶼數(shù)量》非常像但多了一個(gè)關(guān)鍵動作“恢復(fù)現(xiàn)場”**。在《島嶼數(shù)量》中島沉了就沉了但在《單詞搜索》中如果你這一條路沒走通你得把踩過的腳印擦掉給別的路徑留機(jī)會。1. 核心思路DFS 回溯遍歷網(wǎng)格在 的網(wǎng)格里找到第一個(gè)和單詞word[0]匹配的字母作為 DFS 的起點(diǎn)。深度搜索從起點(diǎn)開始向四個(gè)方向擴(kuò)散尋找word[1],word[2]…標(biāo)記與回溯為了防止“同一個(gè)格子重復(fù)使用”我們在進(jìn)入遞歸前把當(dāng)前格子標(biāo)記比如改成空字符。關(guān)鍵點(diǎn)如果這條路最終沒能找到完整的單詞在return之前必須把當(dāng)前格子的字符改回來。這就是回溯。2. 手寫代碼實(shí)現(xiàn)LeetCode 風(fēng)格classSolution:defexist(self,board:list[list[str]],word:str)-bool:rowslen(board)colslen(board[0])defdfs(r,c,k): r, c: 當(dāng)前網(wǎng)格坐標(biāo) k: 當(dāng)前匹配到 word 的第幾個(gè)字符 # 1. 邊界判定 字母匹配判定# 利用短路邏輯先看坐標(biāo)是否越界再看字符是否匹配ifr0orrrowsorc0orccolsorboard[r][c]!word[k]:returnFalse# 2. 成功條件如果匹配到了單詞的最后一個(gè)字母ifklen(word)-1:returnTrue# 3. 標(biāo)記訪問防止原地轉(zhuǎn)圈同一個(gè)格子重復(fù)使用tempboard[r][c]board[r][c]# 臨時(shí)清空# 4. 四個(gè)方向死磕只要有一個(gè)方向通了就返回 True# 注意k1 代表去找下一個(gè)字母res(dfs(r1,c,k1)ordfs(r-1,c,k1)ordfs(r,c1,k1)ordfs(r,c-1,k1))# 5. 回溯擦掉腳印恢復(fù)現(xiàn)場# 無論 res 是 True 還是 False都要把字母還回去board[r][c]tempreturnres# 主邏輯尋找起點(diǎn)forrinrange(rows):forcinrange(cols):ifdfs(r,c,0):returnTruereturnFalse3. 這題和《島嶼數(shù)量》的細(xì)節(jié)差異細(xì)節(jié)島嶼數(shù)量 (Island)單詞搜索 (Word Search)匹配目標(biāo)只要是 ‘1’ 就行必須匹配word[k]遞歸深度直到把整塊島淹沒直到k len(word) - 1標(biāo)記處理永久修改(把 1 變成 0)暫時(shí)修改(回溯時(shí)要改回來)返回值不需要返回 (void)必須返回bool(通了還是沒通)在《島嶼數(shù)量》里我們是把陸地炸掉炸了就炸了但在《單詞搜索》里我們要尋找的是一條特定的路徑。1. 為什么要“標(biāo)記” (步驟 3)假設(shè)你要找單詞ABA而網(wǎng)格里是A - B兩個(gè)格子。你站在第一個(gè)A上匹配成功。此時(shí)你往右走到B匹配成功。接下來你要在B的四周找下一個(gè)A。如果沒有標(biāo)記你會回頭看向左邊那個(gè)剛剛才用過的A。程序會覺得“哎左邊剛好有個(gè)A” 于是判定ABA存在。但這不符合題意因?yàn)橥粋€(gè)格子不能重復(fù)使用。所以我們每踩到一個(gè)格子就要把它暫時(shí)“變成空”讓后面的遞歸看不見它。2. 為什么要“回溯/恢復(fù)現(xiàn)場” (步驟 5)這是最難理解的地方。我們用一個(gè)真實(shí)的例子來說明假設(shè)網(wǎng)格如下你要找單詞ABCE[A] [B] C D [E] F路徑有兩條可能路徑 1A - B - C - … (走不通了沒找到 E)路徑 2A - B - E (成功)關(guān)鍵點(diǎn)來了程序先試探路徑 1。當(dāng)它走到B的時(shí)候它會嘗試往右走去摸C。為了防止回頭它會把B改成空。如果往C走的那條路徹底失敗了程序會回退Return到B這個(gè)位置。如果不恢復(fù)B當(dāng)程序嘗試路徑 2從A走到下面的D或者嘗試其他分身時(shí)它發(fā)現(xiàn)B還是空的原本能通過B到達(dá)E的路因?yàn)橹笆〉膰L試被永久封死了。3. 視覺化流程做實(shí)驗(yàn)想象你是一個(gè)實(shí)驗(yàn)員在一個(gè)培養(yǎng)皿網(wǎng)格里找路徑拿起temp board[r][c]你把當(dāng)前的顯微鏡玻片拿起來觀察。遮住board[r][c] ‘’在這一片放個(gè)遮光板防止等會兒光線亂跳。觀察四周res dfs…看看上下左右能不能接上。放下board[r][c] temp不管觀察結(jié)果如何你走的時(shí)候必須把遮光板拿走把玻片放回原處。因?yàn)橄乱粋€(gè)實(shí)驗(yàn)員另一條路徑的遞歸可能需要用到這片玻片。4. 代碼執(zhí)行的細(xì)節(jié)順序tempboard[r][c]# 1. 記住這里本來是 Bboard[r][c]# 2. 把它涂掉讓遞歸里的下一層看不見它res(dfs...)# 3. 遞歸像分身一樣出去找它們看到的 board[r][c] 都是空的board[r][c]temp# 4. 分身回來了趕緊把 B 涂回來returnres# 5. 帶著結(jié)果向上級匯報(bào)總結(jié)標(biāo)記是為了約束當(dāng)前這一條路徑不走回頭路?；厮菔菫榱瞬挥绊懫渌赡艿穆窂?。面試官追問“回溯的時(shí)間復(fù)雜度很高怎么優(yōu)化”你“對于這道題回溯是必須的但我們可以做剪枝Pruning。比如先統(tǒng)計(jì)網(wǎng)格里各字母的數(shù)量如果網(wǎng)格里A只有 1 個(gè)而單詞里需要 2 個(gè)A直接返回False連 DFS 都不用進(jìn)?！泵嬖嚬俳?jīng)常會問“如果不允許修改原數(shù)組board你該怎么做”回答“我可以維護(hù)一個(gè)同樣大小的二維布爾數(shù)組visited[m][n]或者使用一個(gè)哈希表Set來記錄訪問過的坐標(biāo) ?！?