C++实现LeetCode200.岛屿的数量介绍_F11 - 专业站长和开发者的学习网站

分享到

C++实现LeetCode200.岛屿的数量介绍

C#教程 来源：转载作者：秩名发布时间：2021-07-28 07:37:43 人浏览

摘要

[LeetCode] 200. Number of Islands 岛屿的数量 Given a 2d grid map of1s (land) and0s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume

[LeetCode] 200. Number of Islands 岛屿的数量

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

这道求岛屿数量的题的本质是求矩阵中连续区域的个数，很容易想到需要用深度优先搜索 DFS 来解，我们需要建立一个 visited 数组用来记录某个位置是否被访问过，对于一个为 ‘1' 且未被访问过的位置，递归进入其上下左右位置上为 ‘1' 的数，将其 visited 对应值赋为 true，继续进入其所有相连的邻位置，这样可以将这个连通区域所有的数找出来，并将其对应的 visited 中的值赋 true，找完相邻区域后，将结果 res 自增1，然后再继续找下一个为 ‘1' 且未被访问过的位置，以此类推直至遍历完整个原数组即可得到最终结果，代码如下：

解法一：

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int m = grid.size(), n = grid[0].size(), res = 0;
        vector<vector<bool>> visited(m, vector<bool>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '0' || visited[i][j]) continue;
                helper(grid, visited, i, j);
                ++res;
            }
        }
        return res;
    }
    void helper(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
        if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == '0' || visited[x][y]) return;
        visited[x][y] = true;
        helper(grid, visited, x - 1, y);
        helper(grid, visited, x + 1, y);
        helper(grid, visited, x, y - 1);
        helper(grid, visited, x, y + 1);
    }
};

当然，这种类似迷宫遍历的题目 DFS 和 BFS 两对好基友肯定是形影不离的，那么 BFS 搞起。其实也很简单，就是在遍历到 ‘1' 的时候，且该位置没有被访问过，那么就调用一个 BFS 即可，借助队列 queue 来实现，现将当前位置加入队列，然后进行 while 循环，将队首元素提取出来，并遍历其周围四个位置，若没有越界的话，就将 visited 中该邻居位置标记为 true，并将其加入队列中等待下次遍历即可，参见代码如下：

解法二：

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int m = grid.size(), n = grid[0].size(), res = 0;
        vector<vector<bool>> visited(m, vector<bool>(n));
        vector<int> dirX{-1, 0, 1, 0}, dirY{0, 1, 0, -1};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '0' || visited[i][j]) continue;
                ++res;
                queue<int> q{{i * n + j}};
                while (!q.empty()) {
                    int t = q.front(); q.pop();
                    for (int k = 0; k < 4; ++k) {
                        int x = t / n + dirX[k], y = t % n + dirY[k];
                        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '0' || visited[x][y]) continue;
                        visited[x][y] = true;
                        q.push(x * n + y);
                    }
                }
            }
        }
        return res;
    }
};

Github 同步地址：

类似题目：

参考资料：

您可能感兴趣的文章 :

原文链接 :

Tag : C++(87)

WPF实现窗体亚克力效果的代码

WPF 窗体设置亚克力效果框架使用大于等于.NET40。 Visual Studio 2022。项目使用MIT开源许可协议。 WindowAcrylicBlur设置亚克力颜色。 Opacity设置透
C#非托管泄漏中HEAP_ENTRY的Size对不上解析

一：背景 1. 讲故事前段时间有位朋友在分析他的非托管泄漏时，发现NT堆的_HEAP_ENTRY的 Size 和!heap命令中的 Size 对不上，来咨询是怎么回事？
C#中ArrayList 类的使用介绍

一：ArrayList 类简单说明动态数组ArrayList类在System.Collecions的命名空间下，所以使用时要加入System.Collecions命名空间，而且ArrayList提供添加，
C#使用BinaryFormatter类、ISerializable接口、XmlSeriali

序列化是将对象转换成字节流的过程，反序列化是把字节流转换成对象的过程。对象一旦被序列化，就可以把对象状态保存到硬盘的某个位
C#序列化与反序列化集合对象并进行版本控制

当涉及到跨进程甚至是跨域传输数据的时候，我们需要把对象序列化和反序列化。首先可以使用Serializable特性。 1 2 3 4 5 6 7 8 9 10 11 12 13 14
C#事件中关于sender的用法解读

C#事件sender的小用法开WPF新坑了，看了WPF的炫酷界面，再看看winForm实在是有些惨不忍睹（逃）。后面会开始写一些短的学习笔记。一、什么
在C#程序中注入恶意DLL的方法

一、背景前段时间在训练营上课的时候就有朋友提到一个问题，为什么 Windbg 附加到 C# 程序后，程序就处于中断状态了？它到底是如何实现
基于C#实现一个简单的FTP操作工具

实现功能实现使用FTP上传、下载、重命名、刷新、删除功能开发环境开发工具： Visual Studio 2013 .NET Framework版本：4.5 实现代码 1 2 3 4 5 6 7
C#仿QQ实现简单的截图功能

接上一篇写的截取电脑屏幕，我们在原来的基础上加一个选择区域的功能，实现自定义选择截图。个人比较懒，上一篇的代码就不重新设计
C#实现线性查找算法的介绍

线性查找，肯定是以线性的方式，在集合或数组中查找某个元素。通过代码来理解线性查找什么叫线性?还是在代码中体会吧。首先需要一