一文秒杀所有岛屿题目 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：一文秒杀所有岛屿题目

评论礼仪 见这里，违者直接拉黑。

[Lucas-ljx]

第二题那个 不是会把第二层的那些也变成1吗 但是没有变 搞不清楚了 大佬可以解答一些吗

[Lucas-ljx]

走0,1的时候 1,0为0也为变为1啊 这个代码 有些看不懂了 第二题

[xixi1998]

先把最外围的一圈所有的岛屿找到，变成水。在看整个矩阵里面能形成岛屿的个数。

[MessiahChen]

上面那个老哥，你仔细看一下代码，如果这个格子是水的话就直接return不会往旁边淹，如果是陆地的话当然要往旁边淹，因为这个格子+旁边的陆地形成的就是靠边的岛屿。
意思就是会把第二层的陆地也变成水的情况只会出现在这个陆地本身就属于需要被排除的靠边岛屿的情况

[Lucas-ljx]

你打印一下 坐标就知道了 有一个是1.1 但是1.1肯定不是啊

[Lucas-ljx]

如果这题的0.1的值是0的话 结果就变成1个了
可以deBug试一下

[Days-Go-By]

0,1的值如果是0，那结果肯定是1了啊，那就少了中间那一片了嘛，因为去掉边界岛屿的时候，都会变为水。去掉边界的岛屿，不是去掉边界上的那 一个 陆地格子，所以，相邻的都是岛屿。我猜你可能是这里想错了

[huangpan2507]

封闭岛屿的数量，一来就把四周最外层的变成1,本来靠边有好几个0，你单独把最外层的变成1了，那其他的0会不会被1(由四周的0变成的1)包围，形成独岛呢？

[Days-Go-By]

不是最外层变为1，是靠边的岛屿变为海水，那就不会有独岛了啊

[liqing455]

至于为什么初始调用 dfs 函数时的 dir 参数可以随意写？
这个问题，我理解是因为起始位置是第一个单元格，如果岛屿只有一个单元格的话，只会出现一次，不会有重复的，如果岛屿有多个单元格的话，第一个跟后面任意一个加起来就能够区分了？不知道理解得对不对？望大佬指点

[huangpan2507]

@Days-Go-By 明白了，会把边界的四个方向的邻居全部变成海，所以不会产生独岛。

[labuladong]

@huangpan2507 你是说哪里不能跳转？

[llnancy]

最前面讲dfs遍历二维数组的代码中visited是boolean[][]二维数组吧，一维的boolean[]报错。

[xwfh2000]

我是这样解答子岛屿问题的（C#，运行时间比100%的提交短（力扣英文版））

public int CountSubIslands(int[][] grid1, int[][] grid2)
        {
            int res = 0;
            int m = grid2.Length;
            int n = grid2[0].Length;
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                {
                    if (grid2[i][j] == 1)
                        if (dfs(grid1, grid2, i, j))
                            res++;
                }
            return res;
        }
        public bool dfs(int[][] grid1, int[][] grid2, int i, int j)
        { //true 表示是子岛屿的一部分
            if (i < 0 || j < 0 || i >= grid2.Length || j >= grid2[0].Length)
                return true;
            if (grid2[i][j] == 0)
                return true;
            grid2[i][j] = 0;
            bool up = dfs(grid1, grid2, i - 1, j);
            bool down = dfs(grid1, grid2, i + 1, j);
            bool left = dfs(grid1, grid2, i, j - 1);
            bool right = dfs(grid1, grid2, i, j + 1);
            return up && down && left && right && grid1[i][j] == 1;
        }

思路是将dfs进行改造。

[savvy1st]

这解法喵喵喵，一大早看过算法题，一天轻飘飘

[xxl10000]

厉害

[labuladong]

@savvy1st 哈哈，人才😂

[chengrenfeng]

哎，这些算法真的是很巧妙呢。

[yonggui-yan]

打卡，打卡。
最后一题 不容易想到。

种类去重用hash table 记录已经有的岛屿形状，hash table 的key是岛屿形状的序列化

[BoyuanShao]

东哥，你最后一道题顺序的comment是不是写反了，按顺序来应该是左 右 上 下吧

[labuladong]

我好像没看出来，哪里反了？

[BoyuanShao]

void dfs(int[][] grid, int i, int j) {
    // 递归顺序：
    dfs(grid, i - 1, j); // 上
    dfs(grid, i + 1, j); // 下
    dfs(grid, i, j - 1); // 左
    dfs(grid, i, j + 1); // 右
}

i - 1, i + 1, j - 1, j + 1分别对应的应该是左，右，上，下吧

[labuladong]

没问题啊，i 是行索引，j 是列索引

[BoyuanShao]

哦哦我绕过来了

[MrRunShu]

秒啊

[lpdswing]

如果是不同岛屿的数量II, 岛屿可以翻转呢

[dotJunz]

DFS和回溯区别

对于最后一题不同的岛屿数量，最后提到这里涉及DFS和回溯算法的一个细微差别

根据东哥图论算法基础提到的二者区别，给出下面我自己的理解。

东哥用的是DFS，关注在节点。
回溯算法关注在边，下面给出回溯代码：

int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

void dfs(int[][] grid, int i, int j, StringBuilder sb) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n
        || grid[i][j] == 0) {
        return;
    }
    grid[i][j] = 0;

    for(int k = 1; k <= 4; k++){
        int ni = i + dir[k - 1][0];
        int nj = j + dir[k - 1][1];
        // 前序遍历位置：进入 (ni, nj)
        sb.append(k).append(',');
        dfs(grid, ni, nj, sb);
        // 后序遍历位置：离开 (ni, nj)
        sb.append(-k).append(',');
    }
}

两者区别可以用下图表示

从这里也可以看出为什么东哥说初始调用 dfs 函数时的 dir 参数可以随意写。

[dotJunz]

代码中 k 有问题，修改如下

int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

void dfs(int[][] grid, int i, int j, StringBuilder sb) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n
        || grid[i][j] == 0) {
        return;
    }
    grid[i][j] = 0;

    for(int k = 1; k <= 4; k++){
        int ni = i + dir[k - 1][0];
        int nj = j + dir[k - 1][1];
        // 前序遍历位置：进入 (ni, nj)
        sb.append(k).append(',');
        dfs(grid, ni, nj, sb);
        // 后序遍历位置：离开 (ni, nj)
        sb.append(-k).append(',');
    }
}

[labuladong]

👍

[bruceeewong]

floodfill的思路太有意思了，最后的序列化也很亮，nice

[NOS-AE]

感谢大佬的岛屿框架呜呜呜！

[martin12365]

东哥，在1254，统计封闭岛屿的数目里面，把靠边的岛屿淹没之后，在遍历grid获取封闭岛屿数目的时候，可以不用遍历grid的最外层了，一点点小建议
//遍历更新后的grid，计算封闭岛屿的数量 因为四周(也就是最外面那一层肯定不行，所以我觉得不用遍历)
//定义并且初始化答案
int res = 0;
for(int i=1; i<m-1; i++){
for(int j=1; j<n-1; j++){
if(grid[i][j] ==0){
res++;
dfs(grid,i,j);
}
}
}

[DonkeyBoy001]

越看越觉得东哥牛逼

[xshu216]

子岛屿，为什么不可以用 grid1[r][c]!=grid2[r][c] 去判断一定不是子岛屿？

[Jingzhenzxz]

强

[DreamYuki]

讲得通俗易懂，效率起飞

[udoless]

最后一题不加后续遍历位置是不是也可以？也能区分唯一性？

// 后序遍历位置：离开 (i, j)
sb.append(-dir).append(',');

[hanglearning]

其实不记录撤销也是可以的 - 但如果不记录撤销的话，进入的路径连着0必须一起记录；如果不记录0的路径只记录1，那必须要记录撤销，不然像东哥说的这种情况

grid = [ [1, 0, 0, 0], [1, 1, 0, 0], [0, 0, 1, 1], [0, 0, 1, 0] ]

1和0都记录且不记录撤销的话，两个岛屿路径分别是：
左上角路径 [1, 1, 2, 1, 2, 3, 4, 1, 2, 3, 4, 3, 4]
右下角路径 [1, 1, 2, 1, 2, 3, 4, 3, 4, 1, 2, 3, 4]

如果只记录1且不记录撤销的话，两个岛屿路径就都是：[1,2,4]

以下是我的记录进入0与1的路径不记录撤销且通过的python代码。写成了VSCode的形式，方便debug

def numDistinctIslands(grid) -> int:

unique_islands = set()
rows, cols = len(grid), len(grid[0])

def dfs(r, c, dir):
    nonlocal dirs
    dirs.append(dir)
    if r == -1 or r == rows or c == -1 or c == cols:
        return
    if grid[r][c] == 1:
        grid[r][c] = 0
        dfs(r - 1, c, 1)
        dfs(r + 1, c, 2)
        dfs(r, c - 1, 3)
        dfs(r, c + 1, 4)

for r in range(rows):
    for c in range(cols):
        if grid[r][c] == 1:
            dirs = []
            dfs(r, c, 1)
            unique_islands.add(tuple(dirs))
            

return len(unique_islands)