一个好的网站建设需要多少钱,网络游戏软件开发app,山东工程网站建设,wordpress 心情评论LeetCode 695- 岛屿的最大面积
题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
题目描述#xff1a;给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合#xff0c;这里的「相邻」要求…LeetCode 695- 岛屿的最大面积
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0代表水包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿则返回面积为 0 。
解题思路
思路一深度优先遍历
首先确定递归函数的参数返回值。本题要路径我们直接设置两个全局变量res和tmp这样可以不用写太多参数传递。返回值就是void参数需要图和一个x和y来记录当前在哪个岛屿。下次从这个岛屿开始走的。确定终止条件本题按我们的逻辑先进入循环再判断是否应该终止那么终止条件就是当超出网格范围 或 该岛屿已经是海洋 就终止。单层处理逻辑每次将当前岛屿淹没并且让这片岛屿的面积因为我们是确定了当前是陆地才会进入下层递归。
class Solution {
public:
int res 0;//记录最大面积
int tmp 0;//当前这片岛屿的面积int maxAreaOfIsland(vectorvectorint grid) {for (int i 0; i grid.size(); i) {for (int j 0; j grid[0].size(); j) {if (grid[i][j] 1) {dfs(grid, i, j);//当这次递归结束的时候说明这片岛屿已经全部被淹没了此时我们可以记录一下//这片岛屿的面积并将tmp置为0也就是下一片岛屿从新计算大小res max(res,tmp);tmp 0;}}}return res;}
public:void dfs(vectorvectorint grid, int i, int j) {if (i 0 || j 0 || i grid.size() || j grid[0].size() || grid[i][j] ! 1){return;}grid[i][j] 0;//当前如果是陆地那么就让岛屿大小tmp;dfs(grid, i 1, j);dfs(grid, i - 1, j);dfs(grid, i, j 1);dfs(grid, i, j - 1);}
};
思路二广度优先遍历
与之前一题一样就是多一个计算每片岛屿面积的tmp
class Solution {
public:int res 0;int tmp 0;int dir[4][2] {0,1,1,0,-1,0,0,-1};int maxAreaOfIsland(vectorvectorint grid) {for(int i0;igrid.size();i){for(int j0;jgrid[0].size();j){if(grid[i][j] 1){bfs(grid,i,j);res max(res,tmp);tmp 0;}}}return res;}void bfs(vectorvectorint grid,int x,int y){queuepairint,int que;que.push({x,y});grid[x][y] 0;tmp;//这里也要面积因为第一次进入也淹没了一个小岛屿。while(!que.empty()){pairint,int cur que.front();que.pop();int curx cur.first;int cury cur.second;for(int i0;i4;i){int nextx curx dir[i][0];int nexty cury dir[i][1];if(nextx 0 || nexty 0 || nextx grid.size() || nexty grid[0].size() ||grid[nextx][nexty] ! 1) continue;que.push({nextx,nexty});grid[nextx][nexty] 0;tmp;}}}
}; 总结
深搜和广搜的问题这题的广搜需要注意只要淹没就得加面积的。
LeetCode 1020- 飞地的数量
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述给你一个大小为 m x n 的二进制矩阵 grid 其中 0 表示一个海洋单元格、1 表示一个陆地单元格。一次 移动 是指从一个陆地单元格走到另一个相邻上、下、左、右的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
解题思路
思路一深度优先遍历
首先确定递归函数的参数返回值。本题不需要这些。不过这题我们要设置一个全局变量cango表示是否能走到界外。为false不能走到界外为true则可以走到界外。确定终止条件本题按我们的逻辑先进入循环再判断是否应该终止那么终止条件就是当超出网格范围 或 当前遍历的是海洋 就终止。不过这里需要注意这道题目需要求的是不能走到界外的岛屿的数量。所以终止条件处理的时候有些区别。当出界的时候就将cango设置为true表示可以走出界并返回。当遇到的是海洋就直接返回。
单层处理逻辑每次我们将当前岛屿的值设置为0模拟为被淹没并且去淹没当前节点的上下左右相邻的节点。为1的节点为陆地状态并且将tmp表示相连的岛屿数量加一。在每次递归完出来的时候说明走完了这一片岛屿我们可以看看是否能走出界不能则将tmp 加到res中并且将tmp置为0cango不做操作因为默认不能走出去。可以则将cango置为false并且将tmp置为0。直到这片海域没有岛屿为止。
class Solution {
public:int res 0;int tmp 0;bool cango false;//标记当前这片岛屿能否走到界外void dfs(vectorvectorint grid,int x,int y){//若到达界外则标记为true返回if(x 0 || y 0 || x grid.size() || y grid[0].size()){cango true;return ;}//若是海洋也返回if(grid[x][y] 0) return;//将岛屿淹没grid[x][y] 0;//这片岛屿数量加一tmp ;dfs(grid,x1,y);dfs(grid,x-1,y);dfs(grid,x,y1);dfs(grid,x,y-1);}int numEnclaves(vectorvectorint grid) {int m grid.size(),n grid[0].size();for(int i0;im;i){for(int j0;jn;j){//若遇到岛屿则进行深度优先遍历if(grid[i][j] 1){dfs(grid,i,j);//若标记为不能走到边界则将tmp加到结果中if(cango false){res tmp;//将tmp清零tmp 0;}else{//若无法走到边界则将cango改为默认值falsetmp 0;cango false;}}}}return res;}
};
思路二广度优先遍历
就是多了一个不能走出界则将岛屿数加到结果中的操作。 class Solution {
public:int tmp 0;int res 0;bool cango false;//标记是否能走到界外int dir[4][2] {0,1,1,0,-1,0,0,-1};void bfs(vectorvectorint grid,int x,int y){queuepairint,int que;//存储对组的队列存坐标用的que.push({x,y});//压入当前的坐标grid[x][y] 0;//淹没当前岛屿tmp ;//只要有淹没就tmpwhile(!que.empty()){pairint,int cur que.front();//取出队头元素que.pop();//弹出队头for(int i0;i4;i){//遍历四个方向看是否有岛屿int nextx cur.first dir[i][0];int nexty cur.second dir[i][1];if(nextx 0 || nexty 0 || nextx grid.size() || nexty grid[0].size()){cango true;continue;}if(0 grid[nextx][nexty]) continue;tmp;que.push({nextx,nexty});grid[nextx][nexty] 0;}}}int numEnclaves(vectorvectorint grid) {int m grid.size(),n grid[0].size();for(int i0;im;i){for(int j0;jn;j){if(grid[i][j] 1){bfs(grid,i,j);if(false cango){res tmp;}else{cango false;}tmp 0;}}}return res;}
};
总结
多了一个加岛屿的操作。
