力扣200. 岛屿数量
200. 岛屿数量
过年也太忙了，这几天基本没着家😇😇😇，我也是晚上抽时间做，所以每天比较晚
原题，题目描述：
给了一个用邻接矩阵表示的图，其中1表示陆地，0表示水域，让我计算有多少个岛，连在一起的都算一个岛，🆓上下左右连接才算，斜着不能连接。这个题力扣划到中等，不过力扣的中等题的难度我只能说上下限差得有点多。这题我认为其实是不难的，我看到这题的第一思路就是深度优先搜索，遍历到的点就设为已经遍历过，我们把图里的点改为'2'，这样就行。下面是我的代码：
class Solution {
private int numIslandsNum = 0;
public int numIslands(char[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
numIslandsNum++;
numIslandsDfs(grid, i, j);
}
}
}
return numIslandsNum;
}
public void numIslandsDfs(char[][] grid, int i, int j) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1') {
return;
}
grid[i][j] = '2';
numIslandsDfs(grid, i, j - 1);
numIslandsDfs(grid, i, j + 1);
numIslandsDfs(grid, i - 1, j);
numIslandsDfs(grid, i + 1, j);
}
}
时间复杂度是O(mn)，空间复杂度也是O(mn)，不过遍历一个2维数组无论如何都得O(mn)。提交打败了百分之95，不过我看了一下提交为2ms的人的代码，其实是同一套，只有一点细微差别。代码简单明了。如果不理解的话可以评论区留言。
力扣200. 岛屿数量
https://www.than.pw/archives/%E5%8A%9B%E6%89%A3200.-%E5%B2%9B%E5%B1%BF%E6%95%B0%E9%87%8F