琼海做网站,网站开发平台 eclipse,深圳市建筑工程,天津在哪做网站算法-图BFS/DFS-单词接龙
1 题目概述
1.1 题目出处
https://leetcode-cn.com/problems/number-of-islands
1.2 题目描述
给定两个单词#xff08;beginWord 和 endWord#xff09;和一个字典#xff0c;找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如…算法-图BFS/DFS-单词接龙
1 题目概述
1.1 题目出处
https://leetcode-cn.com/problems/number-of-islands
1.2 题目描述
给定两个单词beginWord 和 endWord和一个字典找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则
每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 说明:
如果不存在这样的转换序列返回 0。 所有单词具有相同的长度。 所有单词只由小写字母组成。 字典中不存在重复的单词。 你可以假设 beginWord 和 endWord 是非空的且二者不相同。 示例 1:
输入: beginWord “hit”, endWord “cog”, wordList [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出: 5
解释: 一个最短转换序列是 “hit” - “hot” - “dot” - “dog” - “cog”, 返回它的长度 5。 示例 2:
输入: beginWord “hit” endWord “cog” wordList [“hot”,“dot”,“dog”,“lot”,“log”]
输出: 0
解释: endWord “cog” 不在字典中所以无法进行转换。
2 图-DFS
2.1 思路
将岛屿分布看做有向图深度遍历该节点的上下左右四个方向。
遍历到一个为’1’的节点时标记为’0’代表已经遍历过下次不再遍历。
2.2 代码
class Solution {public int numIslands(char[][] grid) {int result 0;if(grid null || grid.length 0){return result;}for(int i 0; i grid.length; i){char[] columns grid[i];for(int j 0; j columns.length; j){char c columns[j];if(c 1){dfs(grid, i, j);result;}}}return result;}private void dfs(char[][] grid, int row, int column){char[] columns grid[row];char c columns[column];if(c 0){return;}else{grid[row][column] 0;if(column - 1 -1){dfs(grid, row, column - 1);}if(column 1 columns.length){dfs(grid, row, column 1);}if(row 1 grid.length){dfs(grid, row 1, column);}if(row - 1 -1){dfs(grid, row - 1, column);}}}
}2.3 时间复杂度 O(N*M)
其中 N 和 M 分别为行数和列数。
2.4 空间复杂度
O(N*M)
因为需要递归
3 BFS
3.1 思路
将岛屿分布看做有向图遍历开始后从当前节点广度优先遍历。
3.2 代码
class Solution {private SetString recordSet new HashSet();public int numIslands(char[][] grid) {int result 0;if(grid null || grid.length 0){return result;}for(int i 0; i grid.length; i){char[] columns grid[i];for(int j 0; j columns.length; j){char c columns[j];if(c 1){bfs(grid, i, j);result;}}}return result;}private void bfs(char[][] grid, int row, int column){char[] columns grid[row];char c columns[column];if(c 0){return;}LinkedListint[] coordinateQueue new LinkedList();coordinateQueue.add(new int[]{row, column});// bfswhile(!coordinateQueue.isEmpty()){int[] coordinate coordinateQueue.poll();int i coordinate[0];int j coordinate[1];if(grid[i][j] 0){continue;}grid[i][j] 0;if(j - 1 -1){coordinateQueue.add(new int[]{i, j - 1});}if(j 1 columns.length){coordinateQueue.add(new int[]{i, j 1});}if(i 1 grid.length){coordinateQueue.add(new int[]{i 1, j});}if(i - 1 -1){coordinateQueue.add(new int[]{ i - 1, j});}}}
}3.3 时间复杂度 O(N*M)
其中 N 和 M 分别为行数和列数。
3.4 空间复杂度
O(min(M,N))
最坏情况全是岛屿
4 效率很低的第一版并查集
4.1 思路
做并查集遇到相邻的’1’节点就合并成一个并查集。
最后返回不同的并查集数。
4.2 代码
class Solution {public int numIslands(char[][] grid) {int result 0;if(grid null || grid.length 0){return result;}int[] unionFindSet new int[grid.length * grid[0].length];for(int i 0; i grid.length; i){char[] columns grid[i];for(int j 0; j columns.length; j){char c columns[j];if(c 1){// 初始化岛节点的并查集为index1find(unionFindSet, i * columns.length j);// 连接右侧节点if(j 1 columns.length grid[i][j 1] 1){// 这里需要将二维数组转为一位数组的下标// 所以使用 当前行*列总数得到该行在一位数组中的首个下标// 再加上当前列作为偏移数得到在一维数组的下标union(unionFindSet, i * columns.length j, i * columns.length j 1);}// 连接下侧节点if(i 1 grid.length grid[i1][j] 1){union(unionFindSet, i * columns.length j, (i 1) * columns.length j);}}}}SetInteger filter new HashSet();for(int i : unionFindSet){if(i ! 0){filter.add(i);}}return filter.size();}private void union(int[] unionFindSet, int p, int q){int left find(unionFindSet, p);int right find(unionFindSet, q);if(left right){return;}// 查找出所有和右边元素同一个并查集元素和左边合并for(int i 0; i unionFindSet.length; i){if(unionFindSet[i] right){unionFindSet[i] left;}}}private int find(int[] unionFindSet, int p){if(unionFindSet[p] 0){unionFindSet[p] p 1;}return unionFindSet[p];}
}4.3 时间复杂度 5 并查集-优化
5.1 思路
合并两个不同祖先的节点时将他们的祖先合并为一个即可。
最后遍历计算出不同的祖先数作为结果返回。
在union的时候还采用了压缩路径优化方法提升查找效率。
5.2 代码
class Solution {public int numIslands(char[][] grid) {int result 0;if(grid null || grid.length 0){return result;}int[] unionFindSet new int[grid.length * grid[0].length];// 初始化所有节点的并查集父节点设为自己for(int i 0; i grid.length; i){char[] columns grid[i];for(int j 0; j columns.length; j){unionFindSet[i * columns.length j] i * columns.length j;}}// 下面开始合并岛节点for(int i 0; i grid.length; i){char[] columns grid[i];for(int j 0; j columns.length; j){char c columns[j];if(c 1){// 初始化岛节点的并查集为index1// find(unionFindSet, i * columns.length j);// 连接右侧节点if(j 1 columns.length grid[i][j 1] 1){// 这里需要将二维数组转为一位数组的下标// 所以使用 当前行*列总数得到该行在一位数组中的首个下标// 再加上当前列作为偏移数得到在一维数组的下标union(unionFindSet, i * columns.length j, i * columns.length j 1);}// 连接下侧节点if(i 1 grid.length grid[i1][j] 1){union(unionFindSet, i * columns.length j, (i 1) * columns.length j);}}else{// 海洋节点将他们的父节点设为-1不参与累计unionFindSet[i * columns.length j] -1;}}}// 去重根节点SetInteger filter new HashSet();// 将所有父节点不为-1的节点全部取出并寻找他们的父节点// 只要父节点不为-1就放入过滤器统计for(int i 0; i unionFindSet.length; i){if(unionFindSet[i] -1){continue;}int root find(unionFindSet, i);if(root -1){filter.add(root);}}// 最终返回不重复的根节点数return filter.size();}private void union(int[] unionFindSet, int p, int q){int left find(unionFindSet, p);int right find(unionFindSet, q);// 说明本来就在一个并查集内不用处理if(left right){return;}// 将右边元素的老祖先作为左边元素老祖先的父节点实现联通unionFindSet[left] right;}private int find(int[] unionFindSet, int p){int son p;// 寻找祖先根节点while(p ! unionFindSet[p]){p unionFindSet[p];}// 路径压缩优化将当前节点及祖先节点的父节点都设为祖先根节点// 即将高度压缩为2方便查找while(son ! p){int tmp unionFindSet[son];unionFindSet[son] p;son tmp;}return p;}
}5.3 时间复杂度 参考岛屿数量
5.4 空间复杂度
O(M*N)
参考文档
算法-并查集
