当前位置：首页 > java >正文

代码随想录算法训练营第四十四天

java 2025/8/22 1:50:02

卡码网题目:

99. 岛屿数量
100. 岛屿的最大面积

其他:

今日总结
往期打卡

99. 岛屿数量

跳转: 99. 岛屿数量

学习: 代码随想录公开讲解

问题:

给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

思路:

Flood Fill求连通区域数量,可以使用bfs或dfs遍历地图,bfs需要及时标记,处理时再标记会重复添加.

复杂度:

时间复杂度: $O (nm)$
空间复杂度: $O (nm)$

代码:

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;class Main {private static int ans;private static int[][] DIRECTION = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};private static boolean[][] vis;private static void dfs(int[][] map, int x, int y) {vis[x][y] = true;for (int i = 0; i < 4; i++) {int n = x + DIRECTION[i][0];int m = y + DIRECTION[i][1];if (n < 0 || n >= map.length || m < 0 || m >= map[0].length || vis[n][m]) continue;if (map[n][m] == 1)dfs(map, n, m);}}private static void bfs(int[][] map,int x,int y){Deque<int[]> stack = new ArrayDeque<>();vis[x][y] = true;stack.add(new int[]{x,y});while(!stack.isEmpty()){int l = stack.size();for(int i=0;i<l;i++){int[] position = stack.pollLast();for(int j=0;j<4;j++){int n = position[0] + DIRECTION[j][0];int m = position[1] + DIRECTION[j][1];if (n < 0 || n >= map.length || m < 0 || m >= map[0].length || vis[n][m]) continue;if (map[n][m] == 1){vis[n][m] = true;stack.add(new int[]{n,m});}}}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int M = sc.nextInt();int[][] map = new int[N][M];vis = new boolean[N][M];for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {map[i][j] = sc.nextInt();}}for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (map[i][j] == 0 || vis[i][j]) continue;ans++;bfs(map, i, j);}}System.out.println(ans);}
}

100. 岛屿的最大面积

跳转: 100. 岛屿的最大面积

学习: 代码随想录公开讲解

问题:

给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

思路:

Flood Fill最大求连通区域长度,可以使用bfs或dfs遍历地图,bfs需要及时标记,处理时再标记会重复添加.

复杂度:

时间复杂度: $O (nm)$
空间复杂度: $O (nm)$

代码:

import java.util.*;class Main {private static int ans;private static int[][] DIRECTION = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};private static boolean[][] vis;private static int dfs(int[][] map, int x, int y) {vis[x][y] = true;int l = 0;for (int i = 0; i < 4; i++) {int n = x + DIRECTION[i][0];int m = y + DIRECTION[i][1];if (n < 0 || n >= map.length || m < 0 || m >= map[0].length || vis[n][m]) continue;if (map[n][m] == 1)l+= dfs(map, n, m);}return l;}private static int bfs(int[][] map,int x,int y){Queue<int[]> stack = new LinkedList<>();vis[x][y] = true;int len = 0;stack.add(new int[]{x,y});while(!stack.isEmpty()){int l = stack.size();len+=l;for(int i=0;i<l;i++){int[] position = stack.poll();for(int j=0;j<4;j++){int n = position[0] + DIRECTION[j][0];int m = position[1] + DIRECTION[j][1];if (n < 0 || n >= map.length || m < 0 || m >= map[0].length || vis[n][m]) continue;if (map[n][m] == 1){vis[n][m] = true;stack.add(new int[]{n,m});}}}}return len;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int M = sc.nextInt();int[][] map = new int[N][M];vis = new boolean[N][M];for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {map[i][j] = sc.nextInt();}}for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (map[i][j] == 0 || vis[i][j]) continue;// ans++;int tmp = bfs(map, i, j);     //只要加入队列就代表走过，就需要标记，而不是从队列拿出来的时候再去标记走过。ans = Math.max(tmp,ans);}}System.out.println(ans);}
}