<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                企業??AI智能體構建引擎,智能編排和調試,一鍵部署,支持知識庫和私有化部署方案 廣告
                # 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">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">numIslands</span><span class="hljs-params">(<span class="hljs-params">vector</span><<span class="hljs-params">vector</span><<span class="hljs-keyword">char</span>>>& grid)</span> </span>{ <span class="hljs-keyword">int</span> res = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-params">0</span>;i<grid.size();i++) { <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-params">0</span>;j<grid[<span class="hljs-params">0</span>].size();j++) { <span class="hljs-keyword">if</span>(grid[i][j] == <span class="hljs-string">'1'</span>) { dfs(grid, i, j); res += <span class="hljs-params">1</span>; } } } <span class="hljs-keyword">return</span> res; } <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">dfs</span><span class="hljs-params">(<span class="hljs-params">vector</span><<span class="hljs-params">vector</span><<span class="hljs-keyword">char</span>>>& grid, <span class="hljs-keyword">int</span> i, <span class="hljs-keyword">int</span> j)</span> </span>{ <span class="hljs-title">// edge</span> <span class="hljs-keyword">if</span>(i<<span class="hljs-params">0</span> || i>= grid.size() || j<<span class="hljs-params">0</span> || j>= grid[<span class="hljs-params">0</span>].size() || grid[i][j] != <span class="hljs-string">'1'</span>) { <span class="hljs-keyword">return</span>; } grid[i][j] = <span class="hljs-string">'0'</span>; dfs(grid, i+<span class="hljs-params">1</span>, j); dfs(grid, i<span class="hljs-params">-1</span>, j); dfs(grid, i, j+<span class="hljs-params">1</span>); dfs(grid, i, j<span class="hljs-params">-1</span>); } }; ``` ``` Java Code: ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">numIslands</span><span class="hljs-params">(<span class="hljs-keyword">char</span>[][] grid)</span> </span>{ <span class="hljs-keyword">if</span> (grid == <span class="hljs-keyword">null</span> || grid.length == <span class="hljs-params">0</span> || grid[<span class="hljs-params">0</span>].length == <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">int</span> count = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> row = <span class="hljs-params">0</span>; row < grid.length; row++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> col = <span class="hljs-params">0</span>; col < grid[<span class="hljs-params">0</span>].length; col++) { <span class="hljs-keyword">if</span> (grid[row][col] == <span class="hljs-string">'1'</span>) { dfs(grid, row, col); count++; } } } <span class="hljs-keyword">return</span> count; } <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">dfs</span><span class="hljs-params">(<span class="hljs-keyword">char</span>[][] grid,<span class="hljs-keyword">int</span> row,<span class="hljs-keyword">int</span> col)</span> </span>{ <span class="hljs-keyword">if</span> (row<<span class="hljs-params">0</span>||row== grid.length||col<<span class="hljs-params">0</span>||col==grid[<span class="hljs-params">0</span>].length||grid[row][col]!=<span class="hljs-string">'1'</span>) { <span class="hljs-keyword">return</span>; } grid[row][col] = <span class="hljs-string">'0'</span>; dfs(grid, row-<span class="hljs-params">1</span>, col); dfs(grid, row+<span class="hljs-params">1</span>, col); dfs(grid, row, col+<span class="hljs-params">1</span>); dfs(grid, row, col-<span class="hljs-params">1</span>); } ``` ``` Javascript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=200 lang=javascript * * [200] Number of Islands */</span> <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">helper</span>(<span class="hljs-params">grid, i, j, rows, cols</span>) </span>{ <span class="hljs-keyword">if</span> (i < <span class="hljs-params">0</span> || j < <span class="hljs-params">0</span> || i > rows - <span class="hljs-params">1</span> || j > cols - <span class="hljs-params">1</span> || grid[i][j] === <span class="hljs-string">"0"</span>) <span class="hljs-keyword">return</span>; grid[i][j] = <span class="hljs-string">"0"</span>; helper(grid, i + <span class="hljs-params">1</span>, j, rows, cols); helper(grid, i, j + <span class="hljs-params">1</span>, rows, cols); helper(grid, i - <span class="hljs-params">1</span>, j, rows, cols); helper(grid, i, j - <span class="hljs-params">1</span>, rows, cols); } <span class="hljs-title">/** * @param {character[][]} grid * @return {number} */</span> <span class="hljs-keyword">var</span> numIslands = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">grid</span>) </span>{ <span class="hljs-keyword">let</span> res = <span class="hljs-params">0</span>; <span class="hljs-keyword">const</span> rows = grid.length; <span class="hljs-keyword">if</span> (rows === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">const</span> cols = grid[<span class="hljs-params">0</span>].length; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < rows; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">0</span>; j < cols; j++) { <span class="hljs-keyword">if</span> (grid[i][j] === <span class="hljs-string">"1"</span>) { helper(grid, i, j, rows, cols); res++; } } } <span class="hljs-keyword">return</span> res; }; ``` ``` python code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">numIslands</span><span class="hljs-params">(self, grid: List[List[str]])</span> -> int:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> grid: <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> count = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(grid)): <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(len(grid[<span class="hljs-params">0</span>])): <span class="hljs-keyword">if</span> grid[i][j] == <span class="hljs-string">'1'</span>: self.dfs(grid, i, j) count += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> count <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dfs</span><span class="hljs-params">(self, grid, i, j)</span>:</span> <span class="hljs-keyword">if</span> i < <span class="hljs-params">0</span> <span class="hljs-keyword">or</span> j < <span class="hljs-params">0</span> <span class="hljs-keyword">or</span> i >= len(grid) <span class="hljs-keyword">or</span> j >= len(grid[<span class="hljs-params">0</span>]) <span class="hljs-keyword">or</span> grid[i][j] != <span class="hljs-string">'1'</span>: <span class="hljs-keyword">return</span> grid[i][j] = <span class="hljs-string">'0'</span> self.dfs(grid, i + <span class="hljs-params">1</span>, j) self.dfs(grid, i - <span class="hljs-params">1</span>, j) self.dfs(grid, i, j + <span class="hljs-params">1</span>) self.dfs(grid, i, j - <span class="hljs-params">1</span>) ``` ``` **復雜度分析** - 時間復雜度: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/)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看