• 力扣第200题 岛屿数量 C++ dfs bfs 深搜和广搜 附Java代码

    题目

    200. 岛屿数量

    中等

    相关标签

    深度优先搜索   广度优先搜索   并查集   数组   矩阵

    给你一个由 '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 （深度优先搜索）

    1. 当使用深度优先搜索（DFS）解决岛屿数量问题时，我们从网格的每个位置开始，尝试向四个方向扩展，以找到相邻的陆地。具体来说，对于当前位置 (x, y)，我们首先检查它是否是未访问过的陆地，并且将其标记为已访问。然后，我们继续向当前位置的四个相邻位置进行扩展搜索，如果这些相邻位置也是未访问过的陆地，则将其标记为已访问，并对这些位置再进行 DFS。通过不断地递归调用 DFS，我们可以逐步标记出与当前位置连通的所有陆地。最终，一个完整的 DFS 过程能够探索完整个岛屿的范围。
    2. 在代码中，DFS 函数被设计用来实现上述的搜索过程。通过对每个陆地位置调用 DFS 函数，我们可以找到并标记出一个完整的岛屿。而在主函数 numIslands 中，我们遍历整个网格，对于每个未访问过的陆地（grid[i][j] == '1' && !visited[i][j]），我们将其标记为已访问，并将岛屿数量加一，然后通过调用 DFS 函数来探索并标记出当前岛屿的全部位置。
    3. 这种深度优先搜索的思维方式，类似于一种 "探险" 的过程，从一个位置出发，不断地向着不同的方向探索，直到无法继续为止，然后返回到之前的位置继续探索。通过这种方式，我们可以逐步发现并标记出完整的岛屿，同时统计出岛屿的数量。

    复杂度

            时间复杂度:

                    O(m*n)

    时间复杂度：

    • 在这段代码中，我们需要遍历整个二维网格，假设网格的大小为 mn，那么时间复杂度为 O(mn)。
    • 在 DFS 过程中，最坏情况下，我们可能需要访问所有的陆地位置，因此 DFS 的时间复杂度也为 O(m*n)。

    因此，综合考虑，这段代码的时间复杂度为 O(m*n)。

            空间复杂度

                    O(m*n)

    空间复杂度：

    • 代码中使用了一个二维数组 visited 用来记录每个位置是否已被访问过，其大小与输入的二维网格大小相同，因此空间复杂度为 O(m*n)。
    • 在 DFS 函数的递归调用过程中，栈的深度最大可能达到网格的大小，因此最坏情况下，递归调用的空间复杂度也为 O(m*n)。

    因此，综合考虑，这段代码的空间复杂度为 O(m*n)。

    c++ 代码 一

    1. class Solution {
    2. public:
    3.     int fanxiang[4][2] = {0,1,1,0,-1,0,0,-1};  // 定义方向数组，表示上、下、左、右四个方向的坐标偏移量
    4.  
    5.     // 定义深度优先搜索函数，用于遍历grid中的岛屿
    6.     void dfs(vectorchar>> &grid, vectorbool>> &visited, int x, int y) {
    7.         for (int i = 0; i < 4; i++) {
    8.             int nextx = x + fanxiang[i][0];  // 计算下一个节点的横坐标
    9.             int nexty = y + fanxiang[i][1];  // 计算下一个节点的纵坐标
    10.             // 检查下一个节点是否越界，如果越界则继续下一次循环
    11.             if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size())
    12.                 continue;
    13.             // 如果下一个节点未被访问过且为陆地，则将其标记为已访问，并继续深度优先搜索
    14.             if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') {
    15.                 visited[nextx][nexty] = true;
    16.                 dfs(grid, visited, nextx, nexty);
    17.             }
    18.         }
    19.     }
    20.  
    21.     // 主函数，用于计算岛屿的数量
    22. public:
    23.     int numIslands(vectorchar>>& grid) {
    24.         int n = grid.size();  // 获取网格的行数
    25.         int m = grid[0].size();  // 获取网格的列数
    26.         vectorbool>> visited = vectorbool>>(n, vector<bool>(m, false));  // 初始化访问标记数组
    27.         int ans = 0;  // 初始化岛屿数量
    28.         for (int i = 0; i < n; i++) {
    29.             for (int j = 0; j < m; j++) {
    30.                 if (!visited[i][j] && grid[i][j] == '1') {  // 如果当前节点未被访问且为陆地，则进行深度优先搜索
    31.                     visited[i][j] = true;  // 标记当前节点为已访问
    32.                     ans++;  // 岛屿数量加一
    33.                     dfs(grid, visited, i, j);  // 开始深度优先搜索
    34.                 }
    35.             }
    36.         }
    37.         return ans;  // 返回岛屿数量
    38.     }
    39. };

    思路和解题方法  bfs （广度优先搜索）

    1. 首先，我们遍历给定的二维网格，对于每一个位置 (r, c)，如果该位置的值为 '1'，表示是陆地，则我们开始一个新的岛屿搜索。

    2. 我们将当前位置 (r, c) 标记为已访问，然后从这个位置开始向周围进行扩散搜索。我们使用一个队列 neighbors 来存储相邻的陆地位置。

    3. 在每一次的扩散搜索中，我们取出队列的首部元素 (row, col)，然后探索其上、下、左、右四个方向上的相邻位置。对于每一个相邻位置，如果是陆地且尚未访问过，则将其加入队列，并标记为已访问。

    4. 我们不断重复这个过程，直到队列为空，表示当前岛屿的所有陆地位置都被访问过。此时一个岛屿的搜索结束，我们将岛屿数量加 1。

    5. 最后，我们继续遍历整个网格，重复上述过程，直到所有的位置都被访问过。

    复杂度

            时间复杂度:

                    O(m*n)

            时间复杂度取决于网格中的元素数量。假设网格的行数为 m，列数为 n，那么时间复杂度为 O(m*n)。因为我们需要遍历整个网格，并且对每个元素进行一次搜索。

            空间复杂度

                    O(m*n)

            空间复杂度，最坏情况下，队列 neighbors 可能存储整个岛屿的所有陆地位置，因此空间复杂度可能达到 O(m*n)。

    c++ 代码二

    1. class Solution {
    2. public:
    3.     int numIslands(vectorchar>>& grid) {
    4.         // 获取网格的行数和列数
    5.         int nr = grid.size();
    6.         if (!nr) return 0; // 如果行数为 0，返回岛屿数量为 0
    7.         int nc = grid[0].size();
    8.  
    9.         int num_islands = 0; // 初始化岛屿数量为 0
    10.         for (int r = 0; r < nr; ++r) { // 遍历行
    11.             for (int c = 0; c < nc; ++c) { // 遍历列
    12.                 if (grid[r][c] == '1') { // 如果当前位置是陆地
    13.                     ++num_islands; // 岛屿数量加一
    14.                     grid[r][c] = '0'; // 将当前位置标记为已访问
    15.                     queueint, int>> neighbors; // 创建一个队列用于存储相邻的陆地位置
    16.                     neighbors.push({r, c}); // 将当前位置加入队列
    17.                     while (!neighbors.empty()) { // 当队列不为空时进行循环
    18.                         auto rc = neighbors.front(); // 取出队首元素
    19.                         neighbors.pop(); // 弹出队首元素
    20.                         int row = rc.first, col = rc.second; // 获取行和列坐标
    21.                         // 探索四个方向上的相邻位置，将相邻的陆地位置加入队列，并标记为已访问
    22.                         if (row - 1 >= 0 && grid[row-1][col] == '1') {
    23.                             neighbors.push({row-1, col});
    24.                             grid[row-1][col] = '0';
    25.                         }
    26.                         if (row + 1 < nr && grid[row+1][col] == '1') {
    27.                             neighbors.push({row+1, col});
    28.                             grid[row+1][col] = '0';
    29.                         }
    30.                         if (col - 1 >= 0 && grid[row][col-1] == '1') {
    31.                             neighbors.push({row, col-1});
    32.                             grid[row][col-1] = '0';
    33.                         }
    34.                         if (col + 1 < nc && grid[row][col+1] == '1') {
    35.                             neighbors.push({row, col+1});
    36.                             grid[row][col+1] = '0';
    37.                         }
    38.                     }
    39.                 }
    40.             }
    41.         }
    42.  
    43.         return num_islands; // 返回岛屿数量
    44.     }
    45. };

    Java代码 一

    1. class Solution {
    2.     // 深度优先搜索函数，用于将当前陆地位置及其相邻的陆地全部标记为已访问
    3.     void dfs(char[][] grid, int r, int c) {
    4.         int nr = grid.length;  // 获取网格的行数
    5.         int nc = grid[0].length;  // 获取网格的列数
    6.  
    7.         // 递归结束条件：当前位置超出边界或者当前位置是水域
    8.         if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
    9.             return;
    10.         }
    11.  
    12.         // 将当前位置标记为已访问（即将 '1' 变为 '0'）
    13.         grid[r][c] = '0';
    14.         
    15.         // 对当前位置的上、下、左、右四个方向进行深度优先搜索
    16.         dfs(grid, r - 1, c);
    17.         dfs(grid, r + 1, c);
    18.         dfs(grid, r, c - 1);
    19.         dfs(grid, r, c + 1);
    20.     }
    21.  
    22.     // 主函数，用于计算岛屿数量
    23.     public int numIslands(char[][] grid) {
    24.         if (grid == null || grid.length == 0) {
    25.             return 0;
    26.         }
    27.  
    28.         int nr = grid.length;  // 获取网格的行数
    29.         int nc = grid[0].length;  // 获取网格的列数
    30.         int num_islands = 0;  // 初始化岛屿数量为 0
    31.  
    32.         // 遍历整个网格
    33.         for (int r = 0; r < nr; ++r) {
    34.             for (int c = 0; c < nc; ++c) {
    35.                 // 如果当前位置是陆地
    36.                 if (grid[r][c] == '1') {
    37.                     ++num_islands;  // 岛屿数量加 1
    38.                     dfs(grid, r, c);  // 对当前岛屿进行深度优先搜索，将所有相邻的陆地标记为已访问
    39.                 }
    40.             }
    41.         }
    42.  
    43.         return num_islands;  // 返回岛屿数量
    44.     }
    45. }

    二

    1. class Solution {
    2.     public int numIslands(char[][] grid) {
    3.         if (grid == null || grid.length == 0) {
    4.             return 0;  // 如果网格为空或者行数为0，则返回岛屿数量为0
    5.         }
    6.  
    7.         int nr = grid.length;  // 获取网格的行数
    8.         int nc = grid[0].length;  // 获取网格的列数
    9.         int num_islands = 0;  // 初始化岛屿数量为0
    10.  
    11.         for (int r = 0; r < nr; ++r) {  // 遍历网格的每一行
    12.             for (int c = 0; c < nc; ++c) {  // 遍历网格的每一列
    13.                 if (grid[r][c] == '1') {  // 如果当前位置是陆地
    14.                     ++num_islands;  // 岛屿数量加1
    15.                     grid[r][c] = '0';  // 将当前位置标记为已访问
    16.                     Queue neighbors = new LinkedList<>();  // 创建一个队列用于存储相邻的陆地位置
    17.                     neighbors.add(r * nc + c);  // 将当前位置加入队列
    18.                     while (!neighbors.isEmpty()) {  // 当队列不为空时进行循环
    19.                         int id = neighbors.remove();  // 从队列中取出一个位置
    20.                         int row = id / nc;  // 计算取出位置的行坐标
    21.                         int col = id % nc;  // 计算取出位置的列坐标
    22.                         // 对当前位置的上、下、左、右四个方向进行判断
    23.                         if (row - 1 >= 0 && grid[row-1][col] == '1') {
    24.                             neighbors.add((row-1) * nc + col);  // 将相邻的陆地位置加入队列
    25.                             grid[row-1][col] = '0';  // 将相邻的陆地位置标记为已访问
    26.                         }
    27.                         // 同上
    28.                         if (row + 1 < nr && grid[row+1][col] == '1') {
    29.                             neighbors.add((row+1) * nc + col);
    30.                             grid[row+1][col] = '0';
    31.                         }
    32.                         // 同上
    33.                         if (col - 1 >= 0 && grid[row][col-1] == '1') {
    34.                             neighbors.add(row * nc + col-1);
    35.                             grid[row][col-1] = '0';
    36.                         }
    37.                         // 同上
    38.                         if (col + 1 < nc && grid[row][col+1] == '1') {
    39.                             neighbors.add(row * nc + col+1);
    40.                             grid[row][col+1] = '0';
    41.                         }
    42.                     }
    43.                 }
    44.             }
    45.         }
    46.  
    47.         return num_islands;  // 返回岛屿数量
    48.     }
    49. }

    觉得有用的话可以点点赞，支持一下。

    如果愿意的话关注一下。会对你有更多的帮助。

    每天都会不定时更新哦  >人<  。

  • 相关阅读:
    【一起学Rust | 进阶篇 | reqwest库】纯 Rust 编写的 HTTP 客户端——reqwest
    嵌入式养成计划-29-网络编程----TCP与UDP的基础模型
    铭文是什么？有什么价值？
    go slice使用
    msvcp71.dll丢失的解决方法分享，全面分析msvcp71.dll丢失原因
    数据流图：四大要素全解析！秘密就在这里
    混合方式启动和销毁service梳理
    Https中间人攻击
    ValidatingWebhookConfiguration 设计说明
    计算机毕业设计Java电影周边产品查找系统(源码+系统+mysql数据库+lw文档)
  • 原文地址：https://blog.csdn.net/jgk666666/article/details/134343699