用网站,快速免费建网站,个人网站花多少钱,微网站对比岛屿数量 深搜
题目链接/文章讲解#xff1a;代码随想录
class Solution {// 计算网格中岛屿的数量public int numIslands(char[][] grid) {int sum 0; // 初始化岛屿数量为0// 遍历整个网格for (int i 0; i grid.length; i) {for (int j 0; j grid[0].length…岛屿数量 深搜
题目链接/文章讲解代码随想录
class Solution {// 计算网格中岛屿的数量public int numIslands(char[][] grid) {int sum 0; // 初始化岛屿数量为0// 遍历整个网格for (int i 0; i grid.length; i) {for (int j 0; j grid[0].length; j) {// 如果当前单元格是陆地1则表示发现了一个新的岛屿if (grid[i][j] 1) {sum; // 增加岛屿计数dfs(grid, i, j); // 使用深度优先搜索DFS标记整个岛屿}}}return sum; // 返回岛屿的总数}// 深度优先搜索用于标记连接的陆地public void dfs(char[][] grid, int i, int j) {// 如果索引越界或当前单元格是水0则返回if (i 0 || i grid.length - 1 || j 0 || j grid[0].length - 1 || grid[i][j] 0) {return;}// 将当前单元格标记为水0表示已经访问过grid[i][j] 0;// 递归地检查四个方向上、下、左、右的相邻单元格dfs(grid, i - 1, j); // 上dfs(grid, i 1, j); // 下dfs(grid, i, j - 1); // 左dfs(grid, i, j 1); // 右}
}岛屿数量 广搜
题目链接/文章讲解代码随想录
class Solution {public int numIslands(char[][] grid) {// 创建一个队列用于BFSQueueint[] queue new LinkedList();// 初始化岛屿数量int sum 0;// 遍历整个网格for (int i 0; i grid.length; i) {for (int j 0; j grid[0].length; j) {// 如果当前位置是陆地1if (grid[i][j] 1) {// 发现一个新的岛屿岛屿数量加一sum;// 将当前位置加入队列并标记为已访问0queue.add(new int[]{i, j});grid[i][j] 0;// 开始BFSwhile (!queue.isEmpty()) {// 从队列中取出一个位置int[] cur queue.poll();int x cur[0];int y cur[1];// 检查上方的位置if (x - 1 0 grid[x - 1][y] 1) {queue.add(new int[]{x - 1, y});grid[x - 1][y] 0; // 标记为已访问}// 检查下方的位置if (x 1 grid.length grid[x 1][y] 1) {queue.add(new int[]{x 1, y});grid[x 1][y] 0; // 标记为已访问}// 检查左边的位置if (y - 1 0 grid[x][y - 1] 1) {queue.add(new int[]{x, y - 1});grid[x][y - 1] 0; // 标记为已访问}// 检查右边的位置if (y 1 grid[0].length grid[x][y 1] 1) {queue.add(new int[]{x, y 1});grid[x][y 1] 0; // 标记为已访问}}}}}// 返回岛屿的总数量return sum;}
}岛屿的最大面积
题目链接/文章讲解代码随想录
class Solution {// 主方法用于计算二维网格中最大的岛屿面积public int maxAreaOfIsland(int[][] grid) {int max_area 0; // 初始化最大岛屿面积为0// 遍历整个二维网格for (int i 0; i grid.length; i) {for (int j 0; j grid[0].length; j) {// 如果当前格子是岛屿值为1if (grid[i][j] 1) {// 使用深度优先搜索计算当前岛屿的面积int area dfs(grid, i, j);// 更新最大岛屿面积max_area Math.max(max_area, area);}}}return max_area; // 返回最大岛屿面积}// 深度优先搜索方法用于计算岛屿的面积public int dfs(int[][] grid, int i, int j) {// 检查当前格子是否越界或是否是水域值为0if (i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0) {return 0; // 如果是越界或水域返回面积为0}grid[i][j] 0; // 将当前格子标记为已访问值设为0// 递归计算当前格子上、下、左、右四个方向的岛屿面积int up dfs(grid, i - 1, j); // 上int down dfs(grid, i 1, j); // 下int left dfs(grid, i, j - 1); // 左int right dfs(grid, i, j 1); // 右// 返回当前格子的面积1加上四个方向的面积之和return 1 up down left right;}
}
