廣度優先
#廣度優先含有「廣度優先」共 30 篇內容
全部內容
發佈日期由新至舊
一魚多吃: 從不同方法確認 兩點之間的路徑存在與否今天的一魚三吃系列是透過 兩點之間是否存在一條路徑的題目，來回顧以前學過的DFS、BFS和Disjoint Set，鞏固圖論演算法的知識點。
英文的題目敘述在這裡
題目敘述
給定我們已知n個節點的圖，和圖上的每一條無向邊edges。
請問給定的起點start和終點end是否存在一條路徑可
2024-04-22
9
一魚多吃: 從 島嶼周長 理解 圖論演算法的本質今天的官方每日一題是Island Perimeter島嶼周長，很有趣的一題。
題目非常直觀好懂。也很適合拿來作為多角度複習、回顧圖論演算法的好題目。
英文的題目敘述在這裡
題目敘述
題目會給我們一個二維陣列當作地圖，格子點為1代表陸地，格子點為0代表海洋。
要求我們以四連通N4的方式拜訪
2024-04-19
11
合縱連橫: 從 圖論的應用題 理解BFS背後的本質這篇文章，會帶著大家複習以前學過的BFS框架，
並且以圖論的應用題與概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
BFS 框架 + 演算法 虛擬碼
# Queue 通常初始化成根結點，作為起點
BFS_queue = deque([root])
# 先
2024-04-02
10
圖論變化題: 計算好節點Good node的數目_Leetcode 1448_Leetcode精選75題題目敘述
題目會給定我們一顆二元樹的根結點，要求我們計算這棵樹的好結點Good node有多少個?
好結點Good node的定義:
某個節點v是好結點，假如從Root node根結點 到 結點v沿途的節點值都小於等於節點v的節點值。
如果還是覺得很模糊，看下方的測試範例就可以很清楚了解
2024-02-29
4
圖論應用: 奇偶二元樹 Even Odd Tree_Leetcode #1609題目敘述
題目會給定一棵二元樹的根結點，要求我們判定這是否為一顆合法的奇偶二元樹?
奇偶二元樹的定義:
從上到下依序是第0層、第一層、...、第n層
偶數層裡面的節點值都必須是奇數，而且由左到右嚴格遞增。
奇數層裡面的節點值都必須是偶數，而且由左到右嚴格遞減。
題目的原文敘述
測試
2024-02-29
5
圖論應用: 找出二元樹最後一層最左邊的值 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
圖論應用: 壞掉的橘子 Rotting Oranges_Leetcode #994_精選75題題目敘述
題目會給定一個二維陣列grid，代表每顆橘子分布的位置和初始狀態。
0: 這個格子點沒有東西。
1: 這個格子點有一顆新鮮的橘子。
2: 這個格子點有一顆壞掉的橘子。
壞掉的橘子上面的黴菌，
每隔一個週期，可以向上、下、左、右 N4四連通的格子點感染一次。
請問，最少需要多
2024-02-26
4
DFS+模擬: 組合之和 III Combination Sum III_Leetcode #216 精選75題題目敘述
題目會給我們一個參數k 和 目標值n。
請問我們從1~9內挑k個相異的數字，使得他們的總和為n 的組合數有多少？
挑選時，每個數字必須相異，而且每個數字只能選一次。
題目的原文敘述
測試範例
Example 1:
Input: k = 3, n = 7
Output: [
2024-02-15
3
DFS模擬 撥號鍵盤上的英文子母組合Letter Comb of Phone Num Leetcode #17 精選75題目敘述
題目會給我們一個傳統手機的數字鍵盤 和一個數字鍵的輸入字串digits，要求我們列舉出所有輸入字串digits可能對應到的英文字母的排列。
例如輸入digits="23"
那對應到的英文字母排列就是"ad", "ae", "af", "bd", "be", "bf", "cd", "
2024-02-14
3
進階圖論應用: 解開數字鎖 Open the Lock_Leetcode #752題目敘述
題目會給我們一個4位數字的數字鎖，還有解鎖的密碼target，和陷阱數字deadends(假如遇到的會鎖會直接卡住，不能在撥動轉盤了)。
預設開始的狀態是0000，請問，最少要撥動轉盤幾次才能解鎖?
題目的原文敘述
測試範例
Example 1:
Input: deaden
2024-02-09
5