LeetCode原题链接

岛屿数量

题目描述

给你一个由 ‘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’,我们就去判断这个位置的上下左右的四个位置上是不是还有1，这个就很像二叉树的递归，二叉树递归时，我们会递归左树，递归右树。这个我们去递归上下左右四个位置。

2.代码演示。

 public int numIslands(char[][] grid) {if (grid == null ){return 0;}int num = 0;for (int i = 0 ; i < grid.length;i++){for (int j = 0;j < grid[0].length;j++){//碰到1 再去递归看看周围是不是还有'1'if (grid[i][j] == '1'){num++;processInfect(grid,i,j);}}}return num;}/*** 判断有多少孤岛* @param ints* @param i* @param j* @return*/public static void processInfect(char[][]ints,int i,int j){if (i >= ints.length || j >= ints[0].length){return ;}if (i < 0 || j < 0){return ;}if (ints[i][j] == '0'){return ;}//碰到‘1’把他改成'0' 避免重复去计算。ints[i][j] = '0';//上位置processInfect(ints,i - 1,j);//下processInfect(ints,i + 1,j);//左processInfect(ints,i,j - 1);//右processInfect(ints,i,j + 1);}

并查集解法

1.解题思路

把这个二维数组可以转换成并查集的形式，有’1’的位置我们就初始化成并查集的一个元素。然后把相邻的‘1’全部合并成一块，最后返回还剩几个集合，就是几个岛屿。

2.代码演示

public static int numIslands2(char[][] board) {int row = board.length;int col = board[0].length;UnionFind2 uf = new UnionFind2(board);for (int j = 1; j < col; j++) {if (board[0][j - 1] == '1' && board[0][j] == '1') {uf.union(0, j - 1, 0, j);}}for (int i = 1; i < row; i++) {if (board[i - 1][0] == '1' && board[i][0] == '1') {uf.union(i - 1, 0, i, 0);}}for (int i = 1; i < row; i++) {for (int j = 1; j < col; j++) {if (board[i][j] == '1') {if (board[i][j - 1] == '1') {uf.union(i, j - 1, i, j);}if (board[i - 1][j] == '1') {uf.union(i - 1, j, i, j);}}}}return uf.sets();}//实现并查集public static class UnionFind2 {private int[] parent;private int[] size;private int[] help;//二维数组中，每个单个数组的长度，也就是列的长度private int col;//集合的数量private int sets;//初始化并查集public UnionFind2(char[][] board) {col = board[0].length;sets = 0;int row = board.length;int len = row * col;parent = new int[len];size = new int[len];help = new int[len];for (int r = 0; r < row; r++) {for (int c = 0; c < col; c++) {if (board[r][c] == '1') {int i = index(r, c);parent[i] = i;size[i] = 1;sets++;}}}}// (r,c) -> i 二维数组中的位置转化成一维数组中的下标，// 行号 * 列的长度 + 列所在的位置。private int index(int r, int c) {return r * col + c;}// 原始位置 -> 下标private int find(int i) {int hi = 0;while (i != parent[i]) {help[hi++] = i;i = parent[i];}for (hi--; hi >= 0; hi--) {parent[help[hi]] = i;}return i;}//合并集合public void union(int r1, int c1, int r2, int c2) {int i1 = index(r1, c1);int i2 = index(r2, c2);int f1 = find(i1);int f2 = find(i2);if (f1 != f2) {if (size[f1] >= size[f2]) {size[f1] += size[f2];parent[f2] = f1;} else {size[f2] += size[f1];parent[f1] = f2;}sets--;}}public int sets() {return sets;}}