做网站如何避免侵权,深圳做网站的好公司有哪些,生产管理软件哪个好用,百度推广开户渠道公司岛屿数量
题目描述
力扣200-岛屿数量
给你一个由 1#xff08;陆地#xff09;和 0#xff08;水#xff09;组成的的二维网格#xff0c;请你计算网格中岛屿的数量。
岛屿总是被水包围#xff0c;并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此…岛屿数量
题目描述
力扣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本题思路是用遇到一个没有遍历过的节点陆地计数器就加一然后把该节点陆地所能遍历到的陆地都标记上。在遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。
那么如果把节点陆地所能遍历到的陆地都标记上呢就可以使用 DFSBFS或者并查集。
广度优先搜索 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) {//用于将当前陆地相连的陆地都进行标记Queueint[] 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){//搜索边界索引越界或遍历到了0if(i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0) return;//将这块土地标记为0grid[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) {Queueint[] 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) {Queueint[] 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官网
