【leetcode】力扣200.岛屿数量

文章目录

题目

题目链接:

https://leetcode-cn.com/problems/number-of-islands

给你一个由 '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'

解题思路

第一次遇到这种题可能会不知如何下手,但如果写过一次,下次再遇到一定是印象深刻。

首先,理解题意

题目给了一个二维数组,岛屿的定义是数组中上下左右连接在一起的都是 字符1的区域为一个岛屿,要求出岛屿的数量。

题目给的数据范围是可以暴力的

然后,想思路

既然一个岛屿的字符是相同的,而且连接。那么可以从一个点入手,逐步拓展到整个连接的岛屿。同时将遍历过的岛屿标记,防止下次再遍历到该岛屿的另一个点时重复计算。下面思考详细过程:

1.要以数组中的每个点为入口,进行深入拓展。所以深入拓展就需要用到递归

2.递归函数的参数是什么。

所有的操作都是在二维数组中进行的,所以少不了二维数组grid

在拓展的过程是依据一个点,进行发散式拓展,所以少不了点在二维数组中的位置坐标xy

3.参数目前只能想到这些,那么递归结束的条件是什么。

拓展时,如果遇到字符0,那么该位置一定不是所遍历岛屿包括的位置,所以结束的标志是:遍历到字符0。这还不够,这里只是初步的想法,具体还要到函数基本完成时完善。

4.接下来就是递归函数具体要做的事。

要做的事是拓展,那具体是如何拓展的?因为每个点的周围是1还是0我们不知道,所以需要将周围都试探一遍。每个试探过的点都进行标记,这样防止进入到旁边的点又返回陷入死循环,也防止遍历到这个岛屿的其他点时,再次将从该点拓展重复计算。

这里就发现了上一点的问题,递归结束的条件还需要添加,坐标出界的情况,否则会报错。

于是:

void dfs(vector<vector<char>> &grid, int x, int y) { //这里要传址
	if (坐标出界 || grid[x][y] == '0')
		return ;
	grid[x][y] = '0';	 //将遍历过的点标记
	dfs(grid, x - 1, y); //左边的点
	dfs(grid, x + 1, y); //右边的点
	dfs(grid, x, y - 1); //下面的点
	dfs(grid, x, y + 1); //上面的点
}

对于”入口点“应该不难想了,即遍历二维数组,当遇到字符1时,就是”入口点“。这也是为什么grid数组要传址,这样就不会重复遍历过的岛屿。

还有两种思路是题解的,一种是迭代法。思路是一样的,我就不多说了,但要麻烦一点,时间复杂度也一样。另一种是并查集解法,也比较麻烦,同样没有怎么优化,省略吧。。。

代码

class Solution {
public:
    int n, m;

    void dfs(vector<vector<char>> &grid, int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == '0')
            return ;
        grid[x][y] = '0';
        dfs(grid, x - 1, y);
        dfs(grid, x + 1, y);
        dfs(grid, x, y - 1);
        dfs(grid, x, y + 1);
    }

    int numIslands(vector<vector<char>>& grid) {
        n = grid.size();
        if (n == 0)
            return 0;
        m = grid[0].size();
        int k = 0;
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < m; ++ j) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    k ++;
                }
            }
        }
        return k;
    }
};

总结

这类题属于做一遍下次就会的题,力扣里还有一题类似的:130. 被围绕的区域 。这一题和本题有一点差别,只需要将其四个边的点遍历当“入口点”即可,同时标记为其他的字符。然后遍历所以的点,将除标记字符外的点改为X,标记的改为O即可。多做几题类似的,忘记了回头再看一下,这类题就很容易了。

上一篇:2021 年职业院校技能大赛“网络安全”项目 江西省比赛任务书


下一篇:Java新手入门200例116之Java反射访问构造方法