关于智能合约:DFS-算法秒杀五道岛屿问题

39次阅读

共计 7099 个字符,预计需要花费 18 分钟才能阅读完成。

读完本文,你不仅学会了算法套路,还能够顺便去 LeetCode 上拿下如下题目:

200. 岛屿数量(中等)

1254. 统计关闭岛屿的数目(中等)

1020. 飞地的数量

695. 岛屿的最大面积

1905. 统计子岛屿

694. 不同的岛屿数量

———–

岛屿问题是经典的面试高频题,尽管根本的岛屿问题并不难,然而岛屿问题有一些有意思的扩大,比方求子岛屿数量,求形态不同的岛屿数量等等,本文就来把这些问题一网打尽。

岛屿系列问题的外围考点就是用 DFS/BFS 算法遍历二维数组

本文次要来解说如何用 DFS 算法来秒杀岛屿系列问题,不过用 BFS 算法的外围思路是齐全一样的,无非就是把 DFS 改写成 BFS 而已。

那么如何在二维矩阵中应用 DFS 搜寻呢?如果你把二维矩阵中的每一个地位看做一个节点,这个节点的上下左右四个地位就是相邻节点,那么整个矩阵就能够形象成一幅网状的「图」构造。

依据 学习数据结构和算法的框架思维,齐全能够依据二叉树的遍历框架改写出二维矩阵的 DFS 代码框架:

// 二叉树遍历框架
void traverse(TreeNode root) {traverse(root.left);
    traverse(root.right);
}

// 二维矩阵遍历框架
void dfs(int[][] grid, int i, int j, boolean[] visited) {int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // 超出索引边界
        return;
    }
    if (visited[i][j]) {// 已遍历过 (i, j)
        return;
    }
    // 进入节点 (i, j)
    visited[i][j] = true;
    dfs(grid, i - 1, j); // 上
    dfs(grid, i + 1, j); // 下
    dfs(grid, i, j - 1); // 左
    dfs(grid, i, j + 1); // 右
}

因为二维矩阵实质上是一幅「图」,所以遍历的过程中须要一个 visited 布尔数组避免走回头路,如果你能了解下面这段代码,那么搞定所有岛屿问题都很简略。

这里额定说一个解决二维数组的罕用小技巧,你有时会看到应用「方向数组」来解决上下左右的遍历,和前文 图遍历框架 的代码很相似:

// 方向数组,别离代表上、下、左、右
int[][] dirs = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};

void dfs(int[][] grid, int i, int j, boolean[] visited) {int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // 超出索引边界
        return;
    }
    if (visited[i][j]) {// 已遍历过 (i, j)
        return;
    }

    // 进入节点 (i, j)
    visited[i][j] = true;
    // 递归遍历上下左右的节点
    for (int[] d : dirs) {int next_i = i + d[0];
        int next_j = j + d[1];
        dfs(grid, next_i, next_j);
    }
    // 来到节点 (i, j)
}

这种写法无非就是用 for 循环解决上下左右的遍历罢了,你能够依照集体爱好抉择写法。

岛屿数量

这是力扣第 200 题「岛屿数量」,最简略也是最经典的一道岛屿问题,题目会输出一个二维数组 grid,其中只蕴含 0 或者 10 代表淡水,1 代表海洋,且假如该矩阵周围都是被淡水突围着的。

咱们说连成片的海洋造成岛屿,那么请你写一个算法,计算这个矩阵 grid 中岛屿的个数,函数签名如下:

int numIslands(char[][] grid);

比如说题目给你输出上面这个 grid 有四片岛屿,算法应该返回 4:

思路很简略,关键在于如何寻找并标记「岛屿」,这就要 DFS 算法发挥作用了,咱们间接看解法代码:

// 主函数,计算岛屿数量
int numIslands(char[][] grid) {
    int res = 0;
    int m = grid.length, n = grid[0].length;
    // 遍历 grid
    for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1') {
                // 每发现一个岛屿,岛屿数量加一
                res++;
                // 而后应用 DFS 将岛屿淹了
                dfs(grid, i, j);
            }
        }
    }
    return res;
}

// 从 (i, j) 开始,将与之相邻的海洋都变成淡水
void dfs(char[][] grid, int i, int j) {int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // 超出索引边界
        return;
    }
    if (grid[i][j] == '0') {
        // 曾经是淡水了
        return;
    }
    // 将 (i, j) 变成淡水
    grid[i][j] = '0';
    // 吞没上下左右的海洋
    dfs(grid, i + 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i - 1, j);
    dfs(grid, i, j - 1);
}

为什么每次遇到岛屿,都要用 DFS 算法把岛屿「淹了」呢?次要是为了省事,防止保护 visited 数组

因为 dfs 函数遍历到值为 0 的地位会间接返回,所以只有把通过的地位都设置为 0,就能够起到不走回头路的作用。

PS:这类 DFS 算法还有个别名叫做 FloodFill 算法,当初有没有感觉 FloodFill 这个名字还挺贴切的~

这个最最根本的岛屿问题就说到这,咱们来看看前面的题目有什么花色。

关闭岛屿的数量

上一题说二维矩阵周围能够认为也是被淡水突围的,所以靠边的海洋也算作岛屿。

力扣第 1254 题「统计关闭岛屿的数目」和上一题有两点不同:

1、用 0 示意海洋,用 1 示意淡水。

2、让你计算「关闭岛屿」的数目。所谓「关闭岛屿」就是上下左右全副被 1 突围的 0,也就是说 靠边的海洋不算作「关闭岛屿」

函数签名如下:

int closedIsland(int[][] grid)

比方题目给你输出如下这个二维矩阵:

算法返回 2,只有图中灰色局部的 0 是周围全都被淡水突围着的「关闭岛屿」。

那么如何判断「关闭岛屿」呢?其实很简略,把上一题中那些靠边的岛屿排除掉,剩下的不就是「关闭岛屿」了吗

有了这个思路,就能够间接看代码了,留神这题规定 0 示意海洋,用 1 示意淡水:

// 主函数:计算关闭岛屿的数量
int closedIsland(int[][] grid) {int m = grid.length, n = grid[0].length;
    for (int j = 0; j < n; j++) {
        // 把靠上边的岛屿淹掉
        dfs(grid, 0, j);
        // 把靠下边的岛屿淹掉
        dfs(grid, m - 1, j);
    }
    for (int i = 0; i < m; i++) {
        // 把靠左边的岛屿淹掉
        dfs(grid, i, 0);
        // 把靠右边的岛屿淹掉
        dfs(grid, i, n - 1);
    }
    // 遍历 grid,剩下的岛屿都是关闭岛屿
    int res = 0;
    for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0) {
                res++;
                dfs(grid, i, j);
            }
        }
    }
    return res;
}

// 从 (i, j) 开始,将与之相邻的海洋都变成淡水
void dfs(int[][] grid, int i, int j) {int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {return;}
    if (grid[i][j] == 1) {
        // 曾经是淡水了
        return;
    }
    // 将 (i, j) 变成淡水
    grid[i][j] = 1;
    // 吞没上下左右的海洋
    dfs(grid, i + 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i - 1, j);
    dfs(grid, i, j - 1);
}

只有提前把靠边的海洋都淹掉,而后算进去的就是关闭岛屿了。

PS:解决这类岛屿问题除了 DFS/BFS 算法之外,Union Find 并查集算法也是一种可选的办法,前文 Union Find 算法使用 就用 Union Find 算法解决了一道相似的问题。

这道岛屿题目的解法略微改改就能够解决力扣第 1020 题「飞地的数量」,这题不让你求关闭岛屿的数量,而是求关闭岛屿的面积总和。

其实思路都是一样的,先把靠边的海洋淹掉,而后去数剩下的海洋数量就行了,留神第 1020 题中 1 代表海洋,0 代表淡水:

int numEnclaves(int[][] grid) {int m = grid.length, n = grid[0].length;
    // 淹掉靠边的海洋
    for (int i = 0; i < m; i++) {dfs(grid, i, 0);
        dfs(grid, i, n - 1);
    }
    for (int j = 0; j < n; j++) {dfs(grid, 0, j);
        dfs(grid, m - 1, j);
    }

    // 数一数剩下的海洋
    int res = 0;
    for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1) {res += 1;}
        }
    }

    return res;
}

// 和之前的实现相似
void dfs(int[][] grid, int i, int j) {// ...}

篇幅所限,具体代码我就不写了,咱们持续看其余的岛屿问题。

岛屿的最大面积

这是力扣第 695 题「岛屿的最大面积」,0 示意淡水,1 示意海洋,当初不让你计算岛屿的个数了,而是让你计算最大的那个岛屿的面积,函数签名如下:

int maxAreaOfIsland(int[][] grid)

比方题目给你输出如下一个二维矩阵:

其中面积最大的是橘红色的岛屿,算法返回它的面积 6。

这题的大体思路和之前齐全一样,只不过 dfs 函数吞没岛屿的同时,还应该想方法记录这个岛屿的面积

咱们能够给 dfs 函数设置返回值,记录每次吞没的海洋的个数,间接看解法吧:

int maxAreaOfIsland(int[][] grid) {
    // 记录岛屿的最大面积
    int res = 0;
    int m = grid.length, n = grid[0].length;
    for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1) {
                // 吞没岛屿,并更新最大岛屿面积
                res = Math.max(res, dfs(grid, i, j));
            }
        }
    }
    return res;
}

// 吞没与 (i, j) 相邻的海洋,并返回吞没的海洋面积
int dfs(int[][] grid, int i, int j) {int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // 超出索引边界
        return 0;
    }
    if (grid[i][j] == 0) {
        // 曾经是淡水了
        return 0;
    }
    // 将 (i, j) 变成淡水
    grid[i][j] = 0;

    return dfs(grid, i + 1, j)
         + dfs(grid, i, j + 1)
         + dfs(grid, i - 1, j)
         + dfs(grid, i, j - 1) + 1;
}

解法和之前相比差不多,我也不多说了,接下来的两道岛屿问题是比拟有技巧性的,咱们重点来看一下。

子岛屿数量

如果说后面的题目都是模板题,那么力扣第 1905 题「统计子岛屿」可能得动动脑子了:

这道题的关键在于,如何疾速判断子岛屿?必定能够借助 Union Find 并查集算法 来判断,不过本文重点在 DFS 算法,就不开展并查集算法了。

什么状况下 grid2 中的一个岛屿 Bgrid1 中的一个岛屿 A 的子岛?

当岛屿 B 中所有海洋在岛屿 A 中也是海洋的时候,岛屿 B 是岛屿 A 的子岛。

反过来说,如果岛屿 B 中存在一片海洋,在岛屿 A 的对应地位是淡水,那么岛屿 B 就不是岛屿 A 的子岛

那么,咱们只有遍历 grid2 中的所有岛屿,把那些不可能是子岛的岛屿排除掉,剩下的就是子岛。

根据这个思路,能够间接写出上面的代码:

int countSubIslands(int[][] grid1, int[][] grid2) {int m = grid1.length, n = grid1[0].length;
    for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid1[i][j] == 0 && grid2[i][j] == 1) {
                // 这个岛屿必定不是子岛,淹掉
                dfs(grid2, i, j);
            }
        }
    }
    // 当初 grid2 中剩下的岛屿都是子岛,计算岛屿数量
    int res = 0;
    for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid2[i][j] == 1) {
                res++;
                dfs(grid2, i, j);
            }
        }
    }
    return res;
}

// 从 (i, j) 开始,将与之相邻的海洋都变成淡水
void dfs(int[][] grid, int i, int j) {int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {return;}
    if (grid[i][j] == 0) {return;}

    grid[i][j] = 0;
    dfs(grid, i + 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i - 1, j);
    dfs(grid, i, j - 1);
}

这道题的思路和计算「关闭岛屿」数量的思路有些相似,只不过后者排除那些靠边的岛屿,前者排除那些不可能是子岛的岛屿。

不同的岛屿数量

这是本文的最初一道岛屿题目,作为压轴题,当然是最有意思的。

力扣第 694 题「不同的岛屿数量」,题目还是输出一个二维矩阵,0 示意淡水,1 示意海洋,这次让你计算 不同的 (distinct) 岛屿数量,函数签名如下:

int numDistinctIslands(int[][] grid)

比方题目输出上面这个二维矩阵:

其中有四个岛屿,然而左下角和右上角的岛屿形态雷同,所以不同的岛屿共有三个,算法返回 3。

很显然咱们得想方法把二维矩阵中的「岛屿」进行转化,变成比方字符串这样的类型,而后利用 HashSet 这样的数据结构去重,最终失去不同的岛屿的个数。

如果想把岛屿转化成字符串,说白了就是序列化,序列化说白了就是遍历嘛,前文 二叉树的序列化和反序列化 讲了二叉树和字符串互转,这里也是相似的。

首先,对于形态雷同的岛屿,如果从同一终点登程,dfs 函数遍历的程序必定是一样的

因为遍历程序是写死在你的递归函数外面的,不会动静扭转:

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); // 右
}

所以,遍历程序从某种意义上说就能够用来形容岛屿的形态,比方下图这两个岛屿:

假如它们的遍历程序是:

下,右,上,撤销上,撤销右,撤销下

如果我用别离用 1, 2, 3, 4 代表上下左右,用 -1, -2, -3, -4 代表上下左右的撤销,那么能够这样示意它们的遍历程序:

2, 4, 1, -1, -4, -2

你看,这就相当于是岛屿序列化的后果,只有每次应用 dfs 遍历岛屿的时候生成这串数字进行比拟,就能够计算到底有多少个不同的岛屿了

咱们须要略微革新 dfs 函数,增加一些函数参数以便记录遍历程序:

void dfs(int[][] grid, int i, int j, StringBuilder sb, int dir) {int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n 
        || grid[i][j] == 0) {return;}
    // 前序遍历地位:进入 (i, j)
    grid[i][j] = 0;
    sb.append(dir).append(',');
    
    dfs(grid, i - 1, j, sb, 1); // 上
    dfs(grid, i + 1, j, sb, 2); // 下
    dfs(grid, i, j - 1, sb, 3); // 左
    dfs(grid, i, j + 1, sb, 4); // 右
    
    // 后序遍历地位:来到 (i, j)
    sb.append(-dir).append(',');
}

dir 记录方向,dfs 函数递归完结后,sb 记录着整个遍历程序,其实这就是前文 回溯算法外围套路 说到的回溯算法框架,你看到头来这些算法都是相通的。

有了这个 dfs 函数就好办了,咱们能够间接写出最初的解法代码:

int numDistinctIslands(int[][] grid) {int m = grid.length, n = grid[0].length;
    // 记录所有岛屿的序列化后果
    HashSet<String> islands = new HashSet<>();
    for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1) {
                // 淹掉这个岛屿,同时存储岛屿的序列化后果
                StringBuilder sb = new StringBuilder();
                // 初始的方向能够轻易写,不影响正确性
                dfs(grid, i, j, sb, 666);
                islands.add(sb.toString());
            }
        }
    }
    // 不雷同的岛屿数量
    return islands.size();}

这样,这道题就解决了,至于为什么初始调用 dfs 函数时的 dir 参数能够随便写,这里波及 DFS 和回溯算法的一个细微差别,前文 图算法根底 有写,这里就不开展了。

以上就是全副岛屿系列问题的解题思路,兴许后面的题目大部分人会做,然而最初两题还是比拟奇妙的,心愿本文对你有帮忙。

_____________

查看更多优质算法文章 点击我的头像,手把手带你刷力扣,致力于把算法讲清楚!我的 算法教程 曾经取得 90k star,欢送点赞!

正文完
 0