以网站域名做邮箱,wordpress添加上一篇下一页,做网站赚钱好难,吃什么补肾气效果好目录 题目描述思路及实现方式一#xff1a;深度优先搜索#xff08;DFS#xff09;思路代码实现Java版本C语言版本Python3版本Golang版本 复杂度分析 方式二#xff1a; 使用广度优先搜索#xff08;BFS#xff09;思路代码实现Java实现C实现Python3实现Go实现 总结相似题… 目录 题目描述思路及实现方式一深度优先搜索DFS思路代码实现Java版本C语言版本Python3版本Golang版本 复杂度分析 方式二 使用广度优先搜索BFS思路代码实现Java实现C实现Python3实现Go实现 总结相似题目 标签(题目类型)深度优先搜索DFS、广度优先搜索BFS、并查集Union Find
题目描述
给定一个二维字符网格 map1 表示陆地0 表示水域。网格中的每个1都被视为一个岛屿的一部分被水域包围的1水平或垂直四个方向形成岛屿。找出网格中岛屿的数量。原题LeetCode 200. 岛屿数量
思路及实现
方式一深度优先搜索DFS
思路
使用深度优先搜索DFS遍历每个单元格若遇到陆地’1’则以该点作为起始点开始DFS将与其相连的所有陆地都标记为已访问例如更改为’0’。每次DFS表示遍历了一个完整的岛屿岛屿数量加一。
代码实现
Java版本
public class Solution {private void dfs(char[][] grid, int i, int j) {int m grid.length;int n grid[0].length;// 判断边界条件和是否为陆地if (i 0 || i m || j 0 || j n || grid[i][j] ! 1) {return;}// 标记为已访问水域grid[i][j] 0;// 递归访问上下左右四个方向的相邻陆地dfs(grid, i - 1, j); // 上dfs(grid, i 1, j); // 下dfs(grid, i, j - 1); // 左dfs(grid, i, j 1); // 右}public int numIslands(char[][] grid) {if (grid null || grid.length 0) {return 0;}int m grid.length;int n grid[0].length;int count 0;for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {count;dfs(grid, i, j);}}}return count;}
}说明Java版本使用递归的方式实现了DFS并通过将已访问的陆地标记为’0’来避免重复计数。 C语言版本
#include stdbool.hvoid dfs(char** grid, int gridSize, int* gridColSize, int i, int j) {if (i 0 || i gridSize || j 0 || j gridColSize[0] || grid[i][j] 0) {return;}grid[i][j] 0; // 标记为已访问dfs(grid, gridSize, gridColSize, i - 1, j); // 上dfs(grid, gridSize, gridColSize, i 1, j); // 下dfs(grid, gridSize, gridColSize, i, j - 1); // 左dfs(grid, gridSize, gridColSize, i, j 1); // 右
}int numIslands(char** grid, int gridSize, int* gridColSize){if (grid NULL || gridSize 0 || gridColSize[0] 0) {return 0;}int count 0;for (int i 0; i gridSize; i) {for (int j 0; j gridColSize[0]; j) {if (grid[i][j] 1) {count;dfs(grid, gridSize, gridColSize, i, j);}}}return count;
}说明C语言版本同样使用DFS但需要注意二维数组的传递和边界条件的判断。 Python3版本
class Solution:def dfs(self, grid, i, j):if not 0 i len(grid) or not 0 j len(grid[0]) or grid[i][j] ! 1:returngrid[i][j] 0 # 标记为已访问# 递归访问上下左右四个方向的相邻陆地self.dfs(grid, i - 1, j) # 上self.dfs(grid, i 1, j) # 下self.dfs(grid, i, j - 1) # 左self.dfs(grid, i, j 1) # 右def numIslands(self, grid: List[List[str]]) - int:if not grid:return 0rows, cols len(grid), len(grid[0])count 0for i in range(rows):for j in range(cols):if grid[i][j] 1:count 1self.dfs(grid, i, j)return count说明Python3版本同样使用了DFS但将DFS定义为了类方法并处理了二维列表的边界条件和访问标记。 Golang版本
func dfs(grid [][]byte, i, j int) {rows, cols : len(grid), len(grid[0])if i 0 || i rows || j 0 || j cols || grid[i][j] ! 1 {return}grid[i][j] 0 // 标记为已访问// 递归访问上下左右四个方向的相邻陆地dfs(grid, i-1, j) // 上dfs(grid, i1, j) // 下dfs(grid, i, j-1) // 左dfs(grid, i, j1) // 右
}func numIslands(grid [][]byte) int {if len(grid) 0 {return 0}rows, cols : len(grid), len(grid[0])count : 0for i : 0; i rows; i {for j : 0; j cols; j {if grid[i][j] 1 {countdfs(grid, i, j)}}}return count
}说明Golang版本同样使用了DFS算法但注意在Go中二维数组切片的传递和边界条件判断。 复杂度分析
时间复杂度O(mn)其中m和n分别是网格的行数和列数。因为我们需要遍历整个网格一次并且在每个陆地上都执行DFS操作DFS操作的时间复杂度取决于与当前陆地相连的其他陆地的数量但最坏情况下会遍历完整个网格因此总的时间复杂度是O(mn)。空间复杂度O(mn)DFS栈空间。在最坏的情况下整个网格都是陆地并且所有陆地都相互连接此时DFS的递归调用栈会达到最大深度即网格的面积mn。然而在平均情况下空间复杂度会远小于O(mn)因为大多数DFS调用都会在遇到水域时返回。
方式二 使用广度优先搜索BFS
思路
与DFS类似BFS也通过遍历网格来寻找岛屿。但BFS通常使用队列来存储待访问的节点在这里是网格中的位置。当一个陆地‘1’被访问时我们将其标记为已访问如’0’并将其四个相邻的陆地如果存在加入队列中。我们继续从队列中取出节点直到队列为空这意味着我们已经探索了一个完整的岛屿。然后我们重复这个过程直到所有的陆地都被访问过。
代码实现
Java实现
import java.util.LinkedList;
import java.util.Queue;public class Solution {public int numIslands(char[][] grid) {if (grid null || grid.length 0) return 0;int count 0;int m grid.length;int n grid[0].length;for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {count;bfs(grid, i, j);}}}return count;}private void bfs(char[][] grid, int row, int col) {int m grid.length;int n grid[0].length;// 定义上下左右四个方向的偏移量int[] dx {-1, 1, 0, 0};int[] dy {0, 0, -1, 1};// 使用队列存储待访问的节点Queueint[] queue new LinkedList();queue.offer(new int[]{row, col});// 标记当前节点为已访问grid[row][col] 0;while (!queue.isEmpty()) {int[] curr queue.poll();int x curr[0];int y curr[1];// 遍历四个方向for (int i 0; i 4; i) {int nx x dx[i];int ny y dy[i];// 检查是否越界和是否为陆地且未访问if (nx 0 nx m ny 0 ny n grid[nx][ny] 1) {// 标记为已访问并加入队列grid[nx][ny] 0;queue.offer(new int[]{nx, ny});}}}}
}C实现
#include queue
#include vectorusing namespace std;void bfs(vectorvectorchar grid, int i, int j) {int m grid.size();int n grid[0].size();// 定义上下左右四个方向的偏移量vectorint dx {-1, 1, 0, 0};vectorint dy {0, 0, -1, 1};// 使用队列存储待访问的节点queuepairint, int q;q.push({i, j});// 标记当前节点为已访问grid[i][j] 0;while (!q.empty()) {auto curr q.front();q.pop();int x curr.first;int y curr.second;// 遍历四个方向for (int k 0; k 4; k) {int nx x dx[k];int ny y dy[k];// 检查是否越界和是否为陆地且未访问if (nx 0 nx m ny 0 ny n grid[nx][ny] 1) {// 标记为已访问并加入队列grid[nx][ny] 0;q.push({nx, ny});}}}
}int numIslands(vectorvectorchar grid) {if (grid.empty()) return 0;int m grid.size();int n grid[0].size();int count 0;for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {count;bfs(grid, i, j);}}}return count;
}Python3实现
from collections import dequedef bfs(grid, row, col):m, n len(grid), len(grid[0])directions [(0, 1), (0, -1), (1, 0), (-1, 0)] # 右左下上queue deque([(row, col)])grid[row][col] 0 # 标记为已访问while queue:x, y queue.popleft()for dx, dy in directions:nx, ny x dx, y dyif 0 nx m and 0 ny n and grid[nx][ny] 1:grid[nx][ny] 0 # 标记为已访问queue.append((nx, ny))def numIslands(grid):if not grid:return 0m, n len(grid), len(grid[0])count 0for i in range(m):for j in range(n):if grid[i][j] 1:count 1bfs(grid, i, j)return countGo实现
package mainimport (container/list
)type Point struct {X, Y int
}func bfs(grid [][]byte, row, col int) {m, n : len(grid), len(grid[0])directions : [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} // 上下左右queue : list.New()queue.PushBack(Point{row, col})grid[row][col] 0 // 标记为已访问for queue.Len() 0 {curr : queue.Front().Value.(Point)queue.Remove(queue.Front())for _, dir : range directions {nx, ny : curr.Xdir[0], curr.
总结
方式优点缺点时间复杂度空间复杂度DFS实现简单容易理解在最坏情况下空间复杂度较高O(mn)O(mn)DFS栈空间
相似题目
相似题目难度链接LeetCode 695. 岛屿的最大面积中等LeetCode链接LeetCode 130. 被围绕的区域中等LeetCode链接[LeetCode 1254. 统计封闭岛屿的数目
