力扣题200岛屿数量

admin 管理员组

文章数量: 887007

力扣题200岛屿数量

给你一个由 '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

1.深度优先遍历。找到一个1后，就进行深度搜索，找到这个1属于的整个岛，并且在找到这个岛后，将该岛的所有1重置为0，避免重复计算。进行了多少次深度优先遍历，就说明有多少个岛。

class Solution {public int numIslands(char[][] grid) {if(grid == null || grid.length == 0){return 0;}int row = grid.length;int col = grid[0].length;int numOfIslands = 0;for(int i = 0;i < row;i++){for(int j = 0;j < col;j++){if(grid[i][j] == '1'){//遇到一个1，就说明有一个岛，利用dfs把这个岛走完，并且把1改为0，就不会重复计算岛了。numOfIslands++;dfs(grid,i,j);}}}return numOfIslands;}public void dfs(char[][] grid,int r,int c){int row = grid.length;int col = grid[0].length;if(r < 0 || c < 0 || r >= row || c >= col || grid[r][c] == '0'){//当前位置超出了grid的范围，或者遇到了0，即岛的边界return;}grid[r][c] = '0';//遇到1重置为0//继续搜索找到这个完整的岛dfs(grid,r-1,c);dfs(grid,r+1,c);dfs(grid,r,c-1);dfs(grid,r,c+1);}
}

2.广度优先搜索。如果一个位置为1，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的1都会被重新标记为0。直到队列为空，搜索结束。

class Solution {public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) {//输入无效return 0;}int nr = grid.length;int nc = grid[0].length;int num_islands = 0;for (int r = 0; r < nr; ++r) {//行for (int c = 0; c < nc; ++c) {//列if (grid[r][c] == '1') {++num_islands;grid[r][c] = '0';//将1置为0Queue<Integer> neighbors = new LinkedList<>();//辅助队列，存储一个岛neighbors.add(r * nc + c);while (!neighbors.isEmpty()) {//队列不为空，若队列为空，说明一个岛被遍历完毕了int id = neighbors.remove();int row = id / nc;int col = id % nc;//查找四周是否还存在1if (row - 1 >= 0 && grid[row-1][col] == '1') {neighbors.add((row-1) * nc + col);grid[row-1][col] = '0';}if (row + 1 < nr && grid[row+1][col] == '1') {neighbors.add((row+1) * nc + col);grid[row+1][col] = '0';}if (col - 1 >= 0 && grid[row][col-1] == '1') {neighbors.add(row * nc + col-1);grid[row][col-1] = '0';}if (col + 1 < nc && grid[row][col+1] == '1') {neighbors.add(row * nc + col+1);grid[row][col+1] = '0';}}}}}return num_islands;}
}

3.并查集。为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为1，则将其与相邻四个方向上的1在并查集中进行合并。最终岛屿的数量就是并查集中连通分量的数目。

参考：Java实现并查集_TheSevenSky-CSDN博客_java并查集

        并查集(Java实现) - GoldArowana - 博客园

class Solution {class UnionFind {int count;//记录当前有多少个集合int[] parent;//记录每个节点对应的父节点int[] rank;//记录了当前是根节点时树的深度，以此优化路径public UnionFind(char[][] grid) {//初始化count = 0;int m = grid.length;//行int n = grid[0].length;//列parent = new int[m * n];//该数组存储每个节点属于的集合的代表rank = new int[m * n];for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == '1') {//初始化时，每个1都属于自己的集合parent[i * n + j] = i * n + j;++count;}rank[i * n + j] = 0;//记录每个位置节点在其集合内的深度}}}public int find(int i) {//找到每个位置节点属于的集合的代表if (parent[i] != i) parent[i] = find(parent[i]);return parent[i];}public void union(int x, int y) {//结合两个位置的节点int rootx = find(x);//第一个位置所属集合的代表int rooty = find(y);//第二个位置所属集合的代表if (rootx != rooty) {//如果两个代表不一样，说明不是一个集合里的，进行合并if (rank[rootx] > rank[rooty]) {//如果第一个集合比第二个集合深，相当于集合一比赢了，成为了新的集合的代表parent[rooty] = rootx;} else if (rank[rootx] < rank[rooty]) {//如果第二个集合比第一个集合深，相当于集合二比赢了，成为了新的集合的代表parent[rootx] = rooty;} else {//如果一样深，相当于打平了，就让第一个集合的根节点当代表parent[rooty] = rootx;rank[rootx] += 1;}--count;//因为集合并起来了，数量减1}}public int getCount() {return count;}}public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) {//输入无效return 0;}int nr = grid.length;//行int nc = grid[0].length;//列int num_islands = 0;UnionFind uf = new UnionFind(grid);for (int r = 0; r < nr; ++r) {for (int c = 0; c < nc; ++c) {if (grid[r][c] == '1') {//遇到1，锁门时一个集合grid[r][c] = '0';//将遇到的1重置为0，避免重复计算岛//将上下左右存在的1，放入这个岛的集合中if (r - 1 >= 0 && grid[r-1][c] == '1') {uf.union(r * nc + c, (r-1) * nc + c);}if (r + 1 < nr && grid[r+1][c] == '1') {uf.union(r * nc + c, (r+1) * nc + c);}if (c - 1 >= 0 && grid[r][c-1] == '1') {uf.union(r * nc + c, r * nc + c - 1);}if (c + 1 < nc && grid[r][c+1] == '1') {uf.union(r * nc + c, r * nc + c + 1);}}}}return uf.getCount();//所有集合整理完毕后，返回集合数量}
}

题源：力扣

本文标签： 力扣题200岛屿数量