【Leetcode 筆記】200. Number of Islands

題目解釋

給定一個 m x n 二維 grid，它代表「1」（陸地）和「0」（水）的地圖，返回島嶼的數量。

島嶼 四面環水，相鄰陸地水平或垂直連接而成。您可以假設 grid 的所有四個邊緣都被水包圍。

範例

• 輸入:

  grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
  ]

• 輸出: 1

只有 1 座小島。

最佳解法

套用 圖 + dfs 的模板解決。

不斷的尋找「1」（陸地），把走過的地方改寫成 #，
且 boundry condition 設成遇到 「0」（水）時就 return，
這樣，只要計算 _dfs() 執行結束的次數就可以知道到底有幾個小島了。

程式碼

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        island_count = 0
        ROWS, COLS = len(grid), len(grid[0])

        def _dfs(row, col, grid):
            if (row < 0) or (col < 0) or (row >= ROWS) or (col >= COLS) or \
                (grid

	

				

			
					
					

	 == "#") or (grid

	

				

			
					
					

	 == "0"):
                return
            else:
                grid

	

				

			
					
					

	 = "#"
                _dfs(row - 1, col, grid)
                _dfs(row + 1, col, grid)
                _dfs(row, col - 1, grid)
                _dfs(row, col + 1, grid)

        if not grid:
            return
        else:
            for row in range(ROWS):
                for col in range(COLS):
                    if grid

	

				

			
					
					

	 == "1":
                        _dfs(row, col, grid)
                        island_count += 1

        return island_count

時間複雜度

O(r * c)，r 跟 c 分別是 grid 的 cols 跟 rows 數。

空間複雜度

O(r * c)，r 跟 c 分別是 grid 的 cols 跟 rows 數。

結語

高頻題，務必好好把握❗

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26