代码随想录算法训练Day57|LeetCode200-岛屿数量、LeetCode695-岛屿的最大面积

岛屿数量

题目描述

力扣200-岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 2：

输入：grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]
]
输出：3

本题思路，是用遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。在遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。

那么如果把节点陆地所能遍历到的陆地都标记上呢，就可以使用 DFS，BFS或者并查集。

广度优先搜索 BFS

不少同学用广搜做这道题目的时候，超时了。 这里有一个广搜中很重要的细节：

根本原因是==只要 加入队列就代表 走过，就需要标记，而不是从队列拿出来的时候再去标记走过==。

很多同学可能感觉这有区别吗？

如果从队列拿出节点，再去标记这个节点走过，就会发生下图所示的结果，会导致很多节点重复加入队列。

 `visited[x][y] = true;` 放在的地方，着去取决于我们对 代码中队列的定义，队列中的节点就表示已经走过的节点。 **所以只要加入队列，立即标记该节点走过**。

本题完整广搜代码：

class Solution {private static final int[][] dir = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } }; // 四个方向private void bfs(char[][] grid, boolean[][] visited, int x, int y) {//用于将当前陆地相连的陆地都进行标记Queue<int[]> queue = new LinkedList<>();queue.add(new int[] { x, y });visited[x][y] = true; // 只要加入队列，立刻标记while (!queue.isEmpty()) {int[] cur = queue.poll();int curx = cur[0];// 取出当前节点(curx,cury)int cury = cur[1];// 遍历四个方向，如果相邻节点(nextx,nexty)在网格内切未被访问过，并且其是陆地（1），则将其加入到队列，并将其标记为已访问for (int[] d : dir) {int nextx = curx + d[0];int nexty = cury + d[1];if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length)continue; // 越界了，直接跳过if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') {queue.add(new int[] { nextx, nexty });visited[nextx][nexty] = true; // 只要加入队列立刻标记}}} // 循环直到队列为空，即所有与起始点连通的陆地都被标记为已访问}public int numIslands(char[][] grid) {int n = grid.length;int m = grid[0].length;boolean[][] visited = new boolean[n][m];// 二维布尔数组visited，用于标记网格中每个位置是否已被访问过int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == '1') {// 当前位置 未访问过的且是陆地，岛屿数量+1result++; // 遇到没访问过的陆地，+1bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true}}}return result;}
}

深度优先搜索 DFS—模板

//DFS
class Solution {private int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四个方向private void dfs(char[][] grid, boolean[][] visited, int x, int y) {for (int[] d : dir) {int nextx = x + d[0];int nexty = y + d[1];if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;  // 越界了，直接跳过if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') { // 没有访问过的同时是陆地的visited[nextx][nexty] = true; dfs(grid, visited, nextx, nexty);} }}public int numIslands(char[][] grid) {int n = grid.length;int m = grid[0].length;boolean[][] visited = new boolean[n][m];int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == '1') { visited[i][j] = true;result++; // 遇到没访问过的陆地，+1dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true}}}return result;}
}

下面的代码使用的是深度优先搜索 DFS 的做法。为了统计岛屿数量同时不重复记录，每当我们搜索到一个岛后，就将这个岛 “淹没” —— 将这个岛所占的地方从 “1” 改为 “0”，这样就不用担心后续会重复记录这个岛屿了。而 DFS 的过程就体现在 “淹没” 这一步中。详见代码：

public int numIslands(char[][] grid) {int res = 0; //记录找到的岛屿数量for(int i = 0;i < grid.length;i++){for(int j = 0;j < grid[0].length;j++){//找到“1”，res加一，同时淹没这个岛if(grid[i][j] == '1'){res++;dfs(grid,i,j);}}}return res;
}
//使用DFS“淹没”岛屿
public void dfs(char[][] grid, int i, int j){//搜索边界：索引越界或遍历到了"0"if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;//将这块土地标记为"0"grid[i][j] = '0';//根据"每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成"，对上下左右的相邻顶点进行dfsdfs(grid,i - 1,j);dfs(grid,i + 1,j);dfs(grid,i,j + 1);dfs(grid,i,j - 1);
}

岛屿的最大面积

题目描述

力扣695-岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻（斜角度的不算）。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

示例 2：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

解题思路

这道题目也是 dfs bfs基础类题目，就是搜索每个岛屿上“1”的数量，然后取一个最大的。

本题思路上比较简单，难点其实都是 dfs 和 bfs的理论基础，关于理论基础我在这里都有详细讲解 ：

DFS理论基础(opens new window)

BFS理论基础

根据BFS模板

//BFS
class Solution {private int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 表示四个方向void bfs(char[][] grid, boolean[][] visited, int x, int y) {Queue<int[]> queue = new LinkedList<>(); // 定义队列queue.offer(new int[]{x, y}); // 起始节点加入队列visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点while (!queue.isEmpty()) { // 开始遍历队列里的元素int[] cur = queue.poll(); // 从队列取元素int curx = cur[0];int cury = cur[1]; // 当前节点坐标for (int i = 0; i < 4; i++) { // 开始向当前节点的四个方向左右上下去遍历int nextx = curx + dir[i][0];int nexty = cury + dir[i][1]; // 获取周围四个方向的坐标if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;  // 坐标越界了，直接跳过if (!visited[nextx][nexty]) { // 如果节点没被访问过queue.offer(new int[]{nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问}}}}
}

BFS

//BFS
class Solution {int[][] dir = {{ 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 }};int count;boolean visited[][];public int maxAreaOfIsland(int[][] grid) {int res = 0;visited = new boolean[grid.length][grid[0].length];for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (visited[i][j] == false && grid[i][j] == 1) {count = 0;bfs(grid, i, j);res = Math.max(res, count);}}}return res;}private void bfs(int[][] grid, int x, int y) {Queue<int[]> queue = new LinkedList<>(); // 定义队列queue.offer(new int[] { x, y }); // 起始节点加入队列visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点count++; // 将起始节点也算入岛屿面积中while (!queue.isEmpty()) { // 开始遍历队列里的元素int[] cur = queue.poll(); // 从队列取元素int curx = cur[0];int cury = cur[1]; // 当前节点坐标for (int i = 0; i < 4; i++) { // 开始向当前节点的四个方向左右上下去遍历int nextx = curx + dir[i][0];int nexty = cury + dir[i][1]; // 获取周围四个方向的坐标if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length)continue;if (visited[nextx][nexty] == false && grid[nextx][nexty] == 1) {queue.offer(new int[] { nextx, nexty }); // 队列添加该节点为下一轮要遍历的节点visited[nextx][nexty] = true;count++;}}}}}

根据DFS模板

//DFS
class Solution {private int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四个方向private void dfs(char[][] grid, boolean[][] visited, int x, int y) {for (int[] d : dir) {int nextx = x + d[0];int nexty = y + d[1];if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;  // 越界了，直接跳过if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') { // 没有访问过的同时是陆地的visited[nextx][nexty] = true; dfs(grid, visited, nextx, nexty);} }}public int numIslands(char[][] grid) {int n = grid.length;int m = grid[0].length;boolean[][] visited = new boolean[n][m];int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == '1') { visited[i][j] = true;result++; // 遇到没访问过的陆地，+1dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true}}}return result;}
}

DFS

//DFS
class Solution {private int count;private int[][] dir = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } }; // 四个方向private void dfs(int[][] grid, boolean[][] visited, int x, int y) {for (int[] d : dir) {int nextx = x + d[0];int nexty = y + d[1];if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length)continue; // 越界了，直接跳过if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 没有访问过的 同时 是陆地的visited[nextx][nexty] = true;count++;dfs(grid, visited, nextx, nexty);}}}public int maxAreaOfIsland(int[][] grid) {int n = grid.length;int m = grid[0].length;boolean[][] visited = new boolean[n][m];int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == 1) {count = 1; // 因为dfs处理下一个节点，所以这里遇到陆地了就先计数，dfs处理接下来的相邻陆地visited[i][j] = true;dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 trueresult = Math.max(result, count);}}}return result;}
}

ps:部分图片和代码来自代码随想录和Leetcode官网