0200. 島嶼數量 · ttttt

# 0200. 島嶼數量 ## 題目地址(200. 島嶼數量) <https://leetcode-cn.com/problems/number-of-islands/> ## 題目描述 ``` <pre class="calibre18">``` 給你一個由 '1'（陸地）和 '0'（水）組成的的二維網格，請你計算網格中島嶼的數量。島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。此外，你可以假設該網格的四條邊均被水包圍。示例 1：輸入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 輸出：1 示例 2：輸入：grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 輸出：3 提示： m == grid.length n == grid[i].length 1 <= m, n <= 300 grid[i][j] 的值為 '0' 或 '1' ``` ``` ## 前置知識 - DFS ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路如圖，我們其實就是要求紅色區域的個數，換句話說就是求連續區域的個數。 ![](https://img.kancloud.cn/e7/c3/e7c37d84347295be2b365d3249184d2f_358x484.jpg) 符合直覺的做法是用DFS來解： - 我們需要建立一個 visited 數組用來記錄某個位置是否被訪問過。 - 對于一個為 `1` 且未被訪問過的位置，我們遞歸進入其上下左右位置上為 `1` 的數，將其 visited 變成 true。 - 重復上述過程 - 找完相鄰區域后，我們將結果 res 自增1，然后我們在繼續找下一個為 `1` 且未被訪問過的位置，直至遍歷完. 但是這道題目只是讓我們求連通區域的個數，因此我們其實不需要額外的空間去存儲visited信息。注意到上面的過程，我們對于數字為0的其實不會進行操作的，也就是對我們“沒用”。因此對于已經訪問的元素，我們可以將其置為0即可。 ## 關鍵點解析 - 二維數組DFS解題模板 - 將已經訪問的元素置為0，省去visited的空間開銷 ## 代碼 - 語言支持：C++, Java, JS, python3 C++ Code： ``` <pre class="calibre18">``` class Solution { public: int numIslands(vector<vector<char>>& grid) { int res = 0; for(int i=0;i<grid.size();i++) { for(int j=0;j<grid[0].size();j++) { if(grid[i][j] == '1') { dfs(grid, i, j); res += 1; } } } return res; } void dfs(vector<vector<char>>& grid, int i, int j) { // edge if(i<0 || i>= grid.size() || j<0 || j>= grid[0].size() || grid[i][j] != '1') { return; } grid[i][j] = '0'; dfs(grid, i+1, j); dfs(grid, i-1, j); dfs(grid, i, j+1); dfs(grid, i, j-1); } }; ``` ``` Java Code： ``` <pre class="calibre18">``` public int numIslands(char[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) return 0; int count = 0; for (int row = 0; row < grid.length; row++) { for (int col = 0; col < grid[0].length; col++) { if (grid[row][col] == '1') { dfs(grid, row, col); count++; } } } return count; } private void dfs(char[][] grid,int row,int col) { if (row<0||row== grid.length||col<0||col==grid[0].length||grid[row][col]!='1') { return; } grid[row][col] = '0'; dfs(grid, row-1, col); dfs(grid, row+1, col); dfs(grid, row, col+1); dfs(grid, row, col-1); } ``` ``` Javascript Code: ``` <pre class="calibre18">``` /* * @lc app=leetcode id=200 lang=javascript * * [200] Number of Islands */ function helper(grid, i, j, rows, cols) { if (i < 0 || j < 0 || i > rows - 1 || j > cols - 1 || grid[i][j] === "0") return; grid[i][j] = "0"; helper(grid, i + 1, j, rows, cols); helper(grid, i, j + 1, rows, cols); helper(grid, i - 1, j, rows, cols); helper(grid, i, j - 1, rows, cols); } /** * @param {character[][]} grid * @return {number} */ var numIslands = function(grid) { let res = 0; const rows = grid.length; if (rows === 0) return 0; const cols = grid[0].length; for (let i = 0; i < rows; i++) { for (let j = 0; j < cols; j++) { if (grid[i][j] === "1") { helper(grid, i, j, rows, cols); res++; } } } return res; }; ``` ``` python code: ``` <pre class="calibre18">``` class Solution: def numIslands(self, grid: List[List[str]]) -> int: if not grid: return 0 count = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == '1': self.dfs(grid, i, j) count += 1 return count def dfs(self, grid, i, j): if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1': return grid[i][j] = '0' self.dfs(grid, i + 1, j) self.dfs(grid, i - 1, j) self.dfs(grid, i, j + 1) self.dfs(grid, i, j - 1) ``` ``` **復雜度分析** - 時間復雜度：O(m?n)O(m \* n)O(m?n) - 空間復雜度：O(m?n)O(m \* n)O(m?n) 歡迎關注我的公眾號《腦洞前端》獲取更多更新鮮的LeetCode題解 ![](https://img.kancloud.cn/77/1d/771d6f53e2a51febbcb6fa97f2899ac3_1586x578.jpg) ## 相關題目 - [695. 島嶼的最大面積](https://leetcode-cn.com/problems/max-area-of-island/solution/695-dao-yu-de-zui-da-mian-ji-dfspython3-by-fe-luci/)