小松鼠的演算法解題教學 - DFS 深度優先演算法與題目解析｜方格子 vocus

DFS 深度優先演算法與題目解析

反璞歸真 DFS模擬鏈結串列的四則運算。 Leetcode #2816

題目敘述輸入給定一個鏈結串列，整體看代表一個十進位的數字，各別看每個節點代表每個digit，分別從最高位~最低位個位數。要求我們把原本的數字乘以二，並且以鏈結串列的形式返回答案。原本的英文題目敘述

小松鼠

2024-05-07

15

嵌套娃娃用遞迴解串列化簡題 Leetcode #2487

題目敘述輸入給定一個鏈結串列的head node。要求我們進行化簡，只要某個節點的右手邊存在比較大的節點，就刪除掉。例如 5->2->13->3 5的右手邊有13，所以5刪除掉。 2的右手邊有13，所以2刪除掉。 13的右手邊沒有更大的節點，所以13留著。 3的右手邊沒有更大

小松鼠

2024-05-06

12

觸類旁通: 用 DFS回溯法框架解組合數之和全系列題。

這篇文章，會帶大家快速回顧DFS+回溯法框架(還沒看過或想複習的可以點連結進去)。用DFS+回溯法框架，解開組合數之和 Combination Sum 的全系列題目。幫助讀者鞏固DFS+回溯法框架這個重要的知識點。回顧 DFS+回溯法框架白話的意思 # 列舉所以可能的情況，

小松鼠

2024-04-28

12

一魚多吃: 從不同方法確認兩點之間的路徑存在與否

今天的一魚三吃系列是透過兩點之間是否存在一條路徑的題目，來回顧以前學過的DFS、BFS和Disjoint Set，鞏固圖論演算法的知識點。英文的題目敘述在這裡題目敘述給定我們已知n個節點的圖，和圖上的每一條無向邊edges。請問給定的起點start和終點end是否存在一條路徑可

小松鼠

2024-04-22

9

DFS應用: 在二元樹插入新的一層 Add one row to Tree_Leetcode #623

題目敘述題目會給定一顆二元樹的根結點，要求我們在指定的層樹d，插入新的一層，節點值為v。原本的左、右子樹，就成為新的那一層的左子樹、右子樹。題目的原文敘述測試範例 Example 1: Input: root = [4,2,6,3,1,5], val = 1, depth =

小松鼠

2024-04-16

10

合縱連橫: 從路徑搜索理解DFS背後的本質

這篇文章，會帶著大家複習以前學過的DFS框架，並且以圖論的應用題與概念為核心，貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。 DFS 深度優先搜索框架 def dfs( parameter ): # 邊界條件 if base case or stop cond

小松鼠

2024-04-04

6

合縱連橫: 從路徑和理解 DFS+樹型DP 框架的本質。

這篇文章，會帶著大家複習以前學過的DFS框架結合樹型DP，並且以路徑和Path Sum的概念與應用為核心，貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。 DFS 深度優先搜索框架 def dfs( parameter ): if base case or sto

小松鼠

2024-03-29

10

合縱連橫: 從鏈結串列應用題理解遞回背後的本質

這篇文章，會帶著大家複習以前學過的遞回框架，並且鏈結串列的概念與應用為核心，貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。遞回框架尋找共通模式(common pattern)，對應到演算法的General case 確立初始條件(initial conditio

小松鼠

2024-03-26

12

合縱連橫: DFS+回溯法框架_理解背後的本質

這篇文章，會帶著大家複習以前學過的DFS + 回溯法框架，並且以回溯法為核心，貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個食用的演算法框架。 DFS + 回溯法框架用途: 展開所有可能的路徑(或者說狀態)，並且把符合條件的狀態加入到最終的結果。 def backtrack

小松鼠

2024-03-18

6

圖論應用: 找出二元樹最後一層最左邊的值 Bottom Left Tree Value_Leetcode #513

題目敘述題目會給定一棵二元樹的根結點，要求我們找出這棵二元樹最後一層最左邊的值。題目的原文敘述測試範例 Example 1: Input: root = [2,1,3] Output: 1 Example 2: Input: root = [1,2,3,4,null,5,6

小松鼠

2024-02-28

7

圖論應用題: 樹的路徑總和 Path Sum_Leetcode #112

題目敘述題目會給定一顆二元樹的根結點Root node，和指定的目標值targetSum。問我們能不能從二元樹裡面找到一條從根結點到葉子結點的路徑，其路徑上的節點值總和恰好為targetSum? 可以的話，返回True。無解的話，返回False。題目的原文敘述測試範例 E

小松鼠

2024-01-29

6

一題多解遊戲模擬 Jump Game III 青蛙過河 III Leetcode_#1306

題目敘述題目會給我們一個輸入陣列nums，每個元素值代表那個格子點可以左右位移的固定長度。例如，假設 nums[i] = 3，那麼下一步可以移動到nums[i-3] 或 nums[i+3]這兩個格子點。題目會給定一個起始點start索引位置，請問我們能不能走到內部數值為0的格子點?

小松鼠

2024-01-27

7