本文共 1212 字，大约阅读时间需要 4 分钟。

链接：

大意：

给定一个二维字符矩阵grid，grid中的元素非'0'即'1'。记'1'为陆地，'0'为海域，统计岛屿的个数。岛屿的定义：被海域所围成的一片陆地称之为一个岛屿。规定：在grid四个边界被海域包围。例子：

思路：

这题的思路即找一个图中的连通子图的个数。使用dfs解决。具体思路类似：

从任意一个'1'开始，四周（上下左右）进行dfs。直到回到该点即可知找到了一个图。接下来从下一个'1'开始dfs。

但是这里一个子图的节点被遍历一次就行，因此对于每个被访问到的'1'，假设为grid[i][j]。则将grid[i][j] = '#'。则下次dfs将不会找到该点，同时省去了一个记录是否访问的二维数组空间。

代码：

class Solution {    private int count = 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') {                    count++;                    dfs(grid, i, j);                }            }        }        return count;    }    public void dfs(char[][] grid, int row, int col) {        grid[row][col] = '#'; // grid[row][col] 变为'#'表明该处已被访问 且该处为某一连通子图的一个节点        if (row - 1 >= 0 && grid[row - 1][col] == '1')            dfs(grid, row - 1, col);        if (row + 1 < grid.length && grid[row + 1][col] == '1')            dfs(grid, row + 1, col);        if (col - 1 >= 0 && grid[row][col - 1] == '1')            dfs(grid, row, col - 1);        if (col + 1 < grid[0].length && grid[row][col + 1] == '1')            dfs(grid, row, col + 1);    }}

结果：

结论：

想不通空间效率为什么这么低？？？ 

转载地址：http://yaesi.baihongyu.com/