代码随想录Day 51|题目：99.岛屿数量、100.岛屿的最大面积

news/2024/9/22 16:54:05 标签: 动态规划, 图论, leetcode, 算法

提示：DDU，供自己复习使用。欢迎大家前来讨论~

文章目录

    • 题目一：99. 岛屿数量
    • 思路
      • 深度优先搜索DFS
      • 广度优先搜索BFS
    • 题目二：100. 岛屿的最大面积
      • DFS
      • BFS
    • 总结

题目一：99. 岛屿数量

99. 岛屿数量 (kamacoder.com)

思路

注意题目中每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

也就是说对角线上是不算的， 例如示例二，是三个岛屿，如图：

图一

这道题题目是 DFS，BFS，并查集，基础题目。

本题思路，是用遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。

在遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。

那么如何把节点陆地所能遍历到的陆地都标记上呢，就可以使用 DFS，BFS或者并查集。

深度优先搜索DFS

思路：

  1. 初始化：创建一个变量result来存储岛屿的数量，初始值为0。
  2. 检查边界条件：如果网格为空或没有行，直接返回0。
  3. 双层循环：使用两个嵌套循环遍历网格的每一行和每一列。
  4. 找到陆地：在内层循环中，检查每个单元格是否为’1’。如果是，增加result的值，并对该单元格进行DFS。
  5. DFS函数：DFS函数将遍历当前单元格的所有四个方向（上、下、左、右），如果相邻单元格是陆地（值为’1’）并且没有越界，则递归调用DFS，并标记该单元格为已访问。
  6. 结束条件：当所有单元格都被检查过，返回result作为最终的岛屿数量。

注意：

  • 递归：DFS是递归实现的，每次递归调用都会检查一个方向的相邻单元格。
  • 边界检查：在DFS中，每次移动前都要检查是否会越界，以避免访问数组之外的内存。
  • 标记已访问：在DFS中，一旦访问了一个陆地单元格，就将其标记为已访问（通常是将’1’改为’0’），以避免重复计数。

下面给出两种版本的代码：

  1. 版本一的写法：
    • 在调用DFS之前，先对节点进行合法性检查。
    • 只有当节点是合法的（即在网格范围内且是陆地）时，才调用DFS函数。
    • 这样做可以减少不必要的递归调用，从而提高效率。
  2. 版本二的写法：
    • 不管节点是否合法，都先调用DFS函数。
    • 在DFS函数内部，通过终止条件来判断节点是否合法。
    • 如果节点不合法（例如，是水或者越界），则直接返回，不进行进一步的递归。
    • 这种写法可能在理解上更直观，因为所有的递归逻辑都封装在DFS函数内部。

两种写法的主要区别在于何时进行合法性检查。版本一在调用DFS之前进行检查，而版本二在DFS函数内部进行检查。理论上，版本一的效率可能更高，因为它避免了对不合法节点的递归调用。然而，从代码的可读性角度来看，版本二可能更清晰，因为它将所有的递归逻辑集中在一起。

完整C++代码如下：

// 版本一 
#include <iostream>
#include <vector>
using namespace std;

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过
        if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 没有访问过的 同时 是陆地的

            visited[nextx][nexty] = true;
            dfs(grid, visited, nextx, nexty);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    vector<vector<bool>> visited(n, vector<bool>(m, false));

    int result = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j] && grid[i][j] == 1) {
                visited[i][j] = true;
                result++; // 遇到没访问过的陆地，+1
                dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
            }
        }
    }

    cout << result << endl;
}

为什么 以上代码中的dfs函数，没有终止条件呢？ 感觉递归没有终止很危险。

其实终止条件 就写在了 调用dfs的地方，如果遇到不合法的方向，直接不会去调用dfs。

当然也可以这么写：

// 版本二
#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
    if (visited[x][y] || grid[x][y] == 0) return; // 终止条件：访问过的节点 或者 遇到海水
    visited[x][y] = true; // 标记访问过
    for (int i = 0; i < 4; i++) {
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过
        dfs(grid, visited, nextx, nexty);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    vector<vector<bool>> visited(n, vector<bool>(m, false));

    int result = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j] && grid[i][j] == 1) {
                result++; // 遇到没访问过的陆地，+1
                dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
            }
        }
    }
    cout << result << endl;
}

最后是另一个更清晰简单的思路的C++代码：

#include <vector>
using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) {
            return 0;
        }
        int result = 0;
        int row = grid.size();
        int col = grid[0].size();
        
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    result++;
                    dfs(grid, i, j, row, col);
                }
            }
        }
        return result;
    }

private:
    void dfs(vector<vector<char>>& grid, int x, int y, int row, int col) {
        if (x < 0 || y < 0 || x >= row || y >= col || grid[x][y] == '0') {
            return;
        }
        grid[x][y] = '0'; // 标记为已访问
        dfs(grid, x - 1, y, row, col); // 向上
        dfs(grid, x + 1, y, row, col); // 向下
        dfs(grid, x, y - 1, row, col); // 向左
        dfs(grid, x, y + 1, row, col); // 向右
    }
};

广度优先搜索BFS

BFS和队列数据结构是相辅相成的

本题完整广搜代码：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void bfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
    queue<pair<int, int>> que;
    que.push({x, y});
    visited[x][y] = true; // 只要加入队列，立刻标记
    while(!que.empty()) {
        pair<int ,int> cur = que.front(); que.pop();
        int curx = cur.first;
        int cury = cur.second;
        for (int i = 0; i < 4; i++) {
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1];
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过
            if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {
                que.push({nextx, nexty});
                visited[nextx][nexty] = true; // 只要加入队列立刻标记
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    vector<vector<bool>> visited(n, vector<bool>(m, false));

    int result = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j] && grid[i][j] == 1) {
                result++; // 遇到没访问过的陆地，+1
                bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
            }
        }
    }


    cout << result << endl;
}

另一种解法：

#include <vector>
#include <queue>
#include <iostream>
using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) {
            return 0;
        }
        int result = 0;
        int row = grid.size();
        int col = grid[0].size();
        queue<pair<int, int>> q;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    result++;
                    q.push({i, j});
                    grid[i][j] = '0';  // Mark as visited
                    while (!q.empty()) {
                        auto cur = q.front();
                        q.pop();
                        int x = cur.first;
                        int y = cur.second;

                        // Check and mark neighbors
                        if (x - 1 >= 0 && grid[x - 1][y] == '1') {
                            q.push({x - 1, y});
                            grid[x - 1][y] = '0';
                        }
                        if (y - 1 >= 0 && grid[x][y - 1] == '1') {
                            q.push({x, y - 1});
                            grid[x][y - 1] = '0';
                        }
                        if (x + 1 < row && grid[x + 1][y] == '1') {
                            q.push({x + 1, y});
                            grid[x + 1][y] = '0';
                        }
                        if (y + 1 < col && grid[x][y + 1] == '1') {
                            q.push({x, y + 1});
                            grid[x][y + 1] = '0';
                        }
                    }
                }
            }
        }
        return result;
    }
};

int main() {
    Solution solution;
    vector<vector<char>> grid = {
        {'1', '1', '0', '0', '0'},
        {'0', '1', '1', '0', '0'},
        {'0', '0', '0', '1', '1'},
        {'1', '0', '0', '0', '1'},
        {'0', '1', '1', '0', '0'}
    };
    cout << "Number of islands: " << solution.numIslands(grid) << endl;
    return 0;
}

题目二：100. 岛屿的最大面积

100. 岛屿的最大面积 (kamacoder.com)

DFS

在编写DFS（深度优先搜索）函数时，存在两种常见写法：一种是在DFS函数外部进行合法性检查后再调用DFS，另一种是在DFS函数内部通过终止条件进行判断。

写法一，dfs只处理下一个节点，即在主函数遇到岛屿就计数为1，dfs处理接下来的相邻陆地

// 版本一
#include <iostream>
#include <vector>
using namespace std;
int count;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过
        if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 没有访问过的 同时 是陆地的
            visited[nextx][nexty] = true;
            count++;
            dfs(grid, visited, nextx, nexty);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    int result = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j] && grid[i][j] == 1) {
                count = 1;  // 因为dfs处理下一个节点，所以这里遇到陆地了就先计数，dfs处理接下来的相邻陆地
                visited[i][j] = true;
                dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
                result = max(result, count);
            }
        }
    }
    cout << result << endl;

}

写法二，dfs处理当前节点，即在主函数遇到岛屿就计数为0，dfs处理接下来的全部陆地

dfs

// 版本二
#include <iostream>
#include <vector>
using namespace std;

int count;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
    if (visited[x][y] || grid[x][y] == 0) return; // 终止条件：访问过的节点 或者 遇到海水
    visited[x][y] = true; // 标记访问过
    count++;
    for (int i = 0; i < 4; i++) {
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过
        dfs(grid, visited, nextx, nexty);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));
    int result = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j] && grid[i][j] == 1) {
                count = 0; // 因为dfs处理当前节点，所以遇到陆地计数为0，进dfs之后在开始从1计数
                dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
                result = max(result, count);
            }
        }
    }
    cout << result << endl;
}

两种DFS写法的差异主要在于何时进行岛屿计数：一种是在主函数中遇到新陆地即计数，另一种是将计数完全放在DFS函数内部处理。这种差异导致了不同的代码风格和逻辑结构，也是造成DFS实现方式多样性的根本原因。

BFS

本题BFS代码如下：

class Solution {
private:
    int count;
    int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
    void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
        queue<int> que;
        que.push(x);
        que.push(y);
        visited[x][y] = true; // 加入队列就意味节点是陆地可到达的点
        count++;
        while(!que.empty()) {
            int xx = que.front();que.pop();
            int yy = que.front();que.pop();
            for (int i = 0 ;i < 4; i++) {
                int nextx = xx + dir[i][0];
                int nexty = yy + dir[i][1];
                if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界
                if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 节点没有被访问过且是陆地
                    visited[nextx][nexty] = true;
                    count++;
                    que.push(nextx);
                    que.push(nexty);
                }
            }
        }
    }

public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    count = 0;
                    bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
                    result = max(result, count);
                }
            }
        }
        return result;
    }
};

总结

BFS、DFS、并查集解决岛屿问题

  1. 算法选择：
    • BFS：适用于层级遍历，可以找到最短路径，适合于岛屿问题因为它可以逐层扩展，直到所有相连的陆地都被访问。
    • DFS：适用于深度遍历，可以探索所有可能的路径，适合于岛屿问题因为它可以深入探索每个岛屿直到尽头。
    • 并查集：适用于处理动态连通性问题，通过合并操作来识别和跟踪连通的组件，适合于岛屿问题因为它可以快速判断和合并相连的陆地。
  2. 实现方式：
    • BFS：使用队列存储待访问的节点，逐层访问，每访问一个陆地节点，就将其所有未访问的相邻陆地节点加入队列。
    • DFS：使用递归或栈存储待访问的节点，深入访问，每访问一个陆地节点，就递归地访问其所有未访问的相邻陆地节点。
    • 并查集：使用集合数据结构，每个陆地节点初始时属于自己的集合，当访问到相邻陆地时，通过并查集的合并操作将它们归为同一集合。
  3. 效率和适用性：
    • BFS：在某些情况下可能比DFS更高效，因为它按层次访问，可以更快地找到所有相邻的陆地，但空间复杂度较高。
    • DFS：在递归深度不大的情况下非常高效，但可能会导致栈溢出，特别是在深度很大的网格中。
    • 并查集：在处理大规模数据时通常更高效，因为它减少了重复访问和递归调用，但需要额外的空间来维护集合信息。

http://www.niftyadmin.cn/n/5670616.html

相关文章

Xv6链接器脚本

Xv6链接器脚本

阅读材料 Xv6代码&#xff1a;kernel.ld 链接器脚本&#xff1a;kernel.ld 链接后可执行文件的布局 首先指定输出的可执行文件架构为RISC-V&#xff0c;指定整个内核程序的入口点为_entry&#xff08;定义在entry.S) OUTPUT_ARCH( "riscv" ) ENTRY( _entry ) 指…
阅读更多...
【WPF】02 按钮控件圆角配置及状态切换

【WPF】02 按钮控件圆角配置及状态切换

按钮圆角 先从工具箱里拖进来一个Button控件&#xff0c;然后对这个按钮进行美化。 首先在 xaml 里按钮控件部分 添加如下代码&#xff1a; <Button x:Name"btnLogin" Content"登录" HorizontalAlignment"Center" Margin"0,399,0,0&q…
阅读更多...
C++学习笔记----7、使用类与对象获得高性能（二）---- 理解对象生命周期（7）

C++学习笔记----7、使用类与对象获得高性能（二）---- 理解对象生命周期（7）

13、对象赋值 就像在c中可以将一个int值赋给另一个&#xff0c;也可以将一个对象赋值给另一个对象。例如&#xff0c;下面的代码将MyCell的值赋值给anotherCell: SpreadsheetCell myCell { 5 }, anotherCell; anotherCell myCell; 你可能会说是myCell被“拷贝”给了anotherCe…
阅读更多...
【算法——双指针】

【算法——双指针】

922. 按奇偶排序数组 II 算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili main:vector<int>nums { 3,1,2,4 };int i 0, j 1;int n nums.size() - 1;while (j < nums.size() && i < nums.size()) //如果奇偶任一方排好了&#xff0c;另…
阅读更多...
Python基础 | 在虚拟环境中安装并在指定文件夹中打开Jupyter notebook

Python基础 | 在虚拟环境中安装并在指定文件夹中打开Jupyter notebook

在虚拟环境中安装并在指定文件夹中打开Jupyter notebook 前言一、在虚拟环境下安装Jupyter notebook二、在指定路径下打开Jupyter notebook 前言 Jupyter Notebook 是一个基于 Web 的交互式计算环境&#xff0c;主要功能是将代码、文本、数学方程式、可视化和其他相关元素组合…
阅读更多...
SkyWalking 环境搭建部署

SkyWalking 环境搭建部署

架构简介 skywalking agent : 和业务系统绑定在一起，负责收集各种监控数据skywalking oapservice : 是负责处理监控数据的，比如接受skywalking agent的监控数据，并存储在数据库中;接受skywalking webapp的前端请求，从数据库查询数据，并返回数据给前端。Skywalking oapserv…
阅读更多...
MySQL高阶之存储过程

MySQL高阶之存储过程

什么是存储过程? 存储过程可称为过程化SQL语言&#xff0c;是在普通SQL语句的基础上增加了编程语言的特点&#xff0c;把数据操作语句(DML)和查询语句(DQL)组织在过程化代码中&#xff0c;通过逻辑判断、循环等操作实现复杂计算的程序语言。 换句话说&#xff0c;存储过程其实…
阅读更多...
技术周总结 09.16~09.22 周日(架构 C# 数据库)

技术周总结 09.16~09.22 周日(架构 C# 数据库)

文章目录 一、09.16 周一1.1&#xff09;问题01&#xff1a; 软件质量属性中"质量属性场景"、"质量属性环境分析"、"质量属性效用树"、"质量属性需求用例分析"分别是什么&#xff1f;1.2&#xff09;问题02&#xff1a; 软件质量属性中…
阅读更多...
最新文章

Copyright @ 2022~2023