站长工具app官方下载,网站如何上传到主机,抄袭网站怎么办,关于做好全国网站建设【问题描述】 第200题 岛屿数量
给你一个由 1#xff08;陆地#xff09;和 0#xff08;水#xff09;组成的的二维网格#xff0c;请你计算网格中岛屿的数量。岛屿总是被水包围#xff0c;并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外#xf…【问题描述】 第200题 岛屿数量
给你一个由 1陆地和 0水组成的的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外你可以假设该网格的四条边均被水包围。示例 1:输入:
11110
11010
11000
00000
输出: 1
示例 2:输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
【解答思路】
1. 深度优先遍历
时间复杂度O(N^2) 空间复杂度O(N)
/*** 方法一深度优先遍历*/
public class Solution {// x-1,y// x,y-1 x,y x,y1// x1,y// 方向数组它表示了相对于当前位置的 4 个方向的横、纵坐标的偏移量这是一个常见的技巧private static final int[][] directions {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};// 标记数组标记了 grid 的坐标对应的格子是否被访问过private boolean[][] marked;// grid 的行数private int rows;// grid 的列数private int cols;private char[][] grid;public int numIslands(char[][] grid) {rows grid.length;if (rows 0) {return 0;}cols grid[0].length;this.grid grid;marked new boolean[rows][cols];int count 0;for (int i 0; i rows; i) {for (int j 0; j cols; j) {// 如果是岛屿中的一个点并且没有被访问过// 就进行深度优先遍历if (!marked[i][j] grid[i][j] 1) {count;dfs(i, j);}}}return count;}// 从坐标为 (i,j) 的点开始进行深度优先遍历private void dfs(int i, int j) {marked[i][j] true;// 得到 4 个方向的坐标for (int k 0; k 4; k) {int newX i directions[k][0];int newY j directions[k][1];// 如果不越界、没有被访问过、并且还要是陆地if (inArea(newX, newY) grid[newX][newY] 1 !marked[newX][newY]) {dfs(newX, newY);}}}// 封装成 inArea 方法语义更清晰private boolean inArea(int x, int y) {// 等于号不要忘了return x 0 x rows y 0 y cols;}public static void main(String[] args) {Solution solution new Solution();char[][] grid1 {{1, 1, 1, 1, 0},{1, 1, 0, 1, 0},{1, 1, 0, 0, 0},{0, 0, 0, 0, 0}};int numIslands1 solution.numIslands(grid1);System.out.println(numIslands1);char[][] grid2 {{1, 1, 0, 0, 0},{1, 1, 0, 0, 0},{0, 0, 1, 0, 0},{0, 0, 0, 1, 1}};int numIslands2 solution.numIslands(grid2);System.out.println(numIslands2);}
}
2. 广度优先遍历
时间复杂度O(N) 空间复杂度O(N)
import java.util.LinkedList;/*** 方法二广度优先遍历*/
public class Solution2 {private int rows;private int cols;public int numIslands(char[][] grid) {// x-1,y// x,y-1 x,y x,y1// x1,yint[][] directions {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};rows grid.length;if (rows 0) {return 0;}cols grid[0].length;boolean[][] marked new boolean[rows][cols];int count 0;for (int i 0; i rows; i) {for (int j 0; j cols; j) {// 如果是岛屿中的一个点并且没有被访问过// 从坐标为 (i,j) 的点开始进行广度优先遍历if (!marked[i][j] grid[i][j] 1) {count;LinkedListInteger queue new LinkedList();// 小技巧把坐标转换为一个数字// 否则得用一个数组存在 Python 中可以使用 tuple 存queue.addLast(i * cols j);// 注意这里要标记上已经访问过marked[i][j] true;while (!queue.isEmpty()) {int cur queue.removeFirst();int curX cur / cols;int curY cur % cols;// 得到 4 个方向的坐标for (int k 0; k 4; k) {int newX curX directions[k][0];int newY curY directions[k][1];// 如果不越界、没有被访问过、并且还要是陆地我就继续放入队列放入队列的同时要记得标记已经访问过if (inArea(newX, newY) grid[newX][newY] 1 !marked[newX][newY]) {queue.addLast(newX * cols newY);// 【特别注意】在放入队列以后要马上标记成已经访问过语义也是十分清楚的反正只要进入了队列你迟早都会遍历到它// 而不是在出队列的时候再标记// 【特别注意】如果是出队列的时候再标记会造成很多重复的结点进入队列造成重复的操作这句话如果你没有写对地方代码会严重超时的marked[newX][newY] true;}}}}}}return count;}private boolean inArea(int x, int y) {// 等于号这些细节不要忘了return x 0 x rows y 0 y cols;}public static void main(String[] args) {Solution2 solution2 new Solution2();char[][] grid1 {{1, 1, 1, 1, 0},{1, 1, 0, 1, 0},{1, 1, 0, 0, 0},{0, 0, 0, 0, 0}};int numIslands1 solution2.numIslands(grid1);System.out.println(numIslands1);char[][] grid2 {{1, 1, 0, 0, 0},{1, 1, 0, 0, 0},{0, 0, 1, 0, 0},{0, 0, 0, 1, 1}};int numIslands2 solution2.numIslands(grid2);System.out.println(numIslands2);}
}
3. 并查集
public class Solution {
public int numIslands(char[][] grid) {int rows grid.length;if (rows 0) {return 0;}int cols grid[0].length;int size rows * cols;// 两个方向的方向向量理解为向下和向右的坐标偏移int[][] directions {{1, 0}, {0, 1}};// 1 是认为虚拟的水域UnionFind unionFind new UnionFind(size 1);for (int i 0; i rows; i) {for (int j 0; j cols; j) {if (grid[i][j] 1) {for (int[] direction : directions) {int newX i direction[0];int newY j direction[1];if (newX rows newY cols grid[newX][newY] 1) {unionFind.union(cols * i j, cols * newX newY);}}} else {// 如果不是陆地所有的水域和一个虚拟的水域连接unionFind.union(cols * i j, size);}}}// 减去那个一开始多设置的虚拟的水域return unionFind.count - 1;
}class UnionFind {private int[] parent;private int count;public UnionFind(int n) {this.count n;parent new int[n];for (int i 0; i n; i) {parent[i] i;}}/*** 返回索引为 p 的元素的根结点** param p* return*/public int find(int p) {// 在 find 的时候执行路径压缩while (p ! parent[p]) {// 两步一跳完成路径压缩这里是「隔代压缩」// 说明「隔代压缩」和「按秩合并」选择一个实现即可「隔代压缩」的代码量少所以选它parent[p] parent[parent[p]];p parent[p];}return p;}public boolean connected(int p, int q) {int pRoot find(p);int qRoot find(q);return pRoot qRoot;}public void union(int p, int q) {int pRoot find(p);int qRoot find(q);if (pRoot qRoot) {return;}parent[qRoot] pRoot;// 每次 union 以后连通分量减 1count--;}
}} 【总结】
1. 深度遍历
递归
2. 广度遍历
队列所有加入队列的结点都应该马上被标记为 “已经访问”否则有可能会被重复加入队列
3.并查集学习资料
https://liweiwei1419.gitee.io/leetcode-algo/leetcode-by-tag/union-find/
参考链接https://leetcode-cn.com/problems/number-of-islands/solution/dfs-bfs-bing-cha-ji-python-dai-ma-java-dai-ma-by-l/
