当前位置: 首页 > news >正文

织梦 网站模板动态ip如何做网站

织梦 网站模板,动态ip如何做网站,wordpress无法连接到ftp服务器,网站建设itcaskLeetCode 695- 岛屿的最大面积 题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 题目描述:给你一个大小为 m x n 的二进制矩阵 grid 。 岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求…

LeetCode 695- 岛屿的最大面积

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题目描述:给你一个大小为 m x n 的二进制矩阵 grid 。

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

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

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

解题思路

思路一(深度优先遍历):

  1. 首先确定递归函数的参数,返回值。本题要路径,我们直接设置两个全局变量res和tmp,这样可以不用写太多参数传递。返回值就是void,参数需要图和一个x和y来记录当前在哪个岛屿。下次从这个岛屿开始走的。
  2. 确定终止条件,本题按我们的逻辑,先进入循环再判断是否应该终止,那么终止条件就是:当超出网格范围 或 该岛屿已经是海洋 就终止。
  3. 单层处理逻辑,每次将当前岛屿淹没,并且让这片岛屿的面积++(因为我们是确定了当前是陆地才会进入下层递归)。
class Solution {
public:
int res = 0;//记录最大面积
int tmp = 0;//当前这片岛屿的面积int maxAreaOfIsland(vector<vector<int>>& 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(vector<vector<int>>& 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(vector<vector<int>>& grid) {for(int i=0;i<grid.size();i++){for(int j=0;j<grid[0].size();j++){if(grid[i][j] == 1){bfs(grid,i,j);res = max(res,tmp);tmp = 0;}}}return res;}void bfs(vector<vector<int>> &grid,int x,int y){queue<pair<int,int>> que;que.push({x,y});grid[x][y] = 0;tmp++;//这里也要面积++,因为第一次进入也淹没了一个小岛屿。while(!que.empty()){pair<int,int> cur = que.front();que.pop();int curx = cur.first;int cury = cur.second;for(int i=0;i<4;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 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

解题思路

思路一(深度优先遍历):

  1. 首先确定递归函数的参数,返回值。本题不需要这些。不过这题我们要设置一个全局变量cango表示是否能走到界外。为false不能走到界外,为true则可以走到界外。
  2. 确定终止条件,本题按我们的逻辑,先进入循环再判断是否应该终止,那么终止条件就是:当超出网格范围 当前遍历的是海洋 就终止。不过这里需要注意,这道题目需要求的是不能走到界外的岛屿的数量。所以终止条件处理的时候有些区别。当出界的时候就将cango设置为true表示可以走出界并返回。当遇到的是海洋,就直接返回。
  1. 单层处理逻辑,每次我们将当前岛屿的值设置为0,模拟为被淹没,并且去淹没当前节点的上下左右相邻的节点。为1的节点为陆地状态,并且将tmp++,表示相连的岛屿数量加一。在每次递归完出来的时候,说明走完了这一片岛屿,我们可以看看是否能走出界,不能则将tmp 加到res中,并且将tmp置为0(cango不做操作,因为默认不能走出去)。可以则将cango置为false,并且将tmp置为0。直到这片海域没有岛屿为止。
class Solution {
public:int res = 0;int tmp = 0;bool cango = false;//标记当前这片岛屿能否走到界外void dfs(vector<vector<int>> &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,x+1,y);dfs(grid,x-1,y);dfs(grid,x,y+1);dfs(grid,x,y-1);}int numEnclaves(vector<vector<int>>& grid) {int m = grid.size(),n = grid[0].size();for(int i=0;i<m;i++){for(int j=0;j<n;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(vector<vector<int>> &grid,int x,int y){queue<pair<int,int>> que;//存储对组的队列,存坐标用的que.push({x,y});//压入当前的坐标grid[x][y] = 0;//淹没当前岛屿tmp ++;//只要有淹没,就tmp++while(!que.empty()){pair<int,int> cur = que.front();//取出队头元素que.pop();//弹出队头for(int i=0;i<4;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(vector<vector<int>>& grid) {int m = grid.size(),n = grid[0].size();for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j] == 1){bfs(grid,i,j);if(false == cango){res += tmp;}else{cango = false;}tmp = 0;}}}return res;}
};

总结:

  • 多了一个加岛屿的操作。
http://www.yayakq.cn/news/80801/

相关文章:

  • 企业国际网站建设app开发和网站开发一样么
  • 论文引用网站数据 如何做注释建网站和建网页的区别
  • 交通局网站建设方案网站做app服务端
  • 在建设网站入账电商运营培训课程
  • 领地申请的网站能备案吗济南网站建设富库网络
  • 为什么做网站费用贵蚌埠百度做网站
  • wordpress主题转html和田地seo
  • 常州网站设计平台江阴做网站
  • 什么网站可以快速做3d效果图茶具网站模板
  • 手机网站php开发百度站长平台账号
  • 阿里云增加网站石青淘宝推广工具
  • 石河子市住房和城乡建设局网站wordpress适合做博客的主题
  • 在线学习网站建设石家庄市网站建设
  • 做网站的技术风险宁波网络推广渠道有哪些
  • 免费的个人空间建网站淘宝放单网站怎么做的
  • 做网站的素材包含哪些招聘信息设计
  • 淘宝建站服务google关键词分析工具
  • 做磁性材料在哪些网站推广比较好长沙优化网站服务
  • 91大神网站建设重庆餐饮加盟网站建设
  • 做美陈3d模型网站wordpress网站如何迁移
  • 网站首页修改中国移动采购与招标网
  • 常州app网站html编辑器安卓版手机版软件
  • 专业网站制作仪表多少钱c2c网站的主要功能
  • 做网站建设怎么介绍自己哪个网站做布料好
  • 网站推广怎么做比较好wordpress hankin
  • 怎么做直播网站超管网站后台登录域名
  • 营销型网站建设iop外网通过域名访问内网服务器
  • 网站地图生成工具贸易公司
  • 网站备案拍照背景幕布网络基础架构
  • 自己开网站怎么开免费咨询产科医生