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

幼儿园主题网络图设计 王菲谷歌优化是什么意思

幼儿园主题网络图设计 王菲,谷歌优化是什么意思,随州网站建设厂家,此网站域名三天更换❓ 1020. 飞地的数量 难度:中等 给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个 海洋单元格、1 表示一个 陆地单元格。 一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边…

❓ 1020. 飞地的数量

难度:中等

给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个 海洋单元格1 表示一个 陆地单元格

一次 移动 是指从一个陆地单元格走到另一个相邻()的陆地单元格或跨过 grid 的边界。

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

示例 1:

在这里插入图片描述

输入:grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出:3
解释:有三个 1 被 0 包围。一个 1 没有被包围,因为它在边界上。

示例 2:

在这里插入图片描述

输入:grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出:0
解释:所有 1 都在边界上或可以到达边界。

提示

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 500
  • grid[i][j] 的值为 01

💡思路:DFS

本题要求找到不靠边的陆地面积,那么

  • 我们只要从周边找到陆地
  • 然后 通过 dfs 或者 bfs 将周边靠陆地且相邻的陆地都变成海洋
  • 然后再去重新遍历地图的时候,统计此时还剩下的陆地就可以了。

🍁代码:(C++、Java)

C++

class Solution {
private:int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向int m = 0, n = 0;void dfs(int i, int j, vector<vector<int>>& grid){if(grid[i][j] == 0){ // 是海洋则返回return;}grid[i][j] = 0;for(int k = 0; k < 4; k++){ // 向四个方向遍历int nexti = i + dir[k][0];int nextj = j + dir[k][1];if(nexti < 0 || nexti >= m || nextj < 0 || nextj >= n) continue;dfs(nexti, nextj, grid);}}
public:int numEnclaves(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();// 从左侧边,和右侧边 向中间遍历for(int i = 0; i < m; i++){dfs(i, 0, grid);dfs(i, n - 1, grid);}// 从上边和下边 向中间遍历for(int i = 0; i < n; i++){dfs(0, i, grid);dfs(m - 1, i, grid);}//统计剩余陆地的面积int ans = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == 1) ans++;}}return ans;}
};

Java

class Solution {private int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; // 四个方向int m = 0, n = 0;private void dfs(int i, int j, int[][] grid){if(grid[i][j] == 0) return;// 是海洋则返回grid[i][j] = 0;for(int k = 0; k < 4; k++){// 向四个方向遍历int nexti = i + dir[k][0];int nextj = j + dir[k][1];// 超过边界if(nexti < 0 || nexti >= m || nextj < 0 || nextj >= n) continue;dfs(nexti, nextj, grid);}}public int numEnclaves(int[][] grid) {m = grid.length;n = grid[0].length;// 从左侧边,和右侧边 向中间遍历for(int i = 0; i < m; i++){dfs(i, 0, grid);dfs(i, n - 1, grid);}// 从上边和下边 向中间遍历for(int j = 0; j < n; j++){dfs(0, j, grid);dfs(m - 1, j, grid);}//统计剩余陆地的面积int ans = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == 1) ans++;}}return ans;}
}

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( m n ) O(mn) O(mn),其中mn 分别是网格 grid 的行数和列数。深度优先搜索最多访问每个单元格一次,需要 O ( m n ) O(mn) O(mn) 的时间,遍历网格统计飞地的数量也需要 O ( m n ) O(mn) O(mn) 的时间。

  • 空间复杂度 O ( m n ) O(mn) O(mn),空间复杂度主要取决于递归调用栈空间,最大空间复杂度是 O ( m n ) O(mn) O(mn)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!

http://www.hrbkazy.com/news/24561.html

相关文章:

  • 有网站前台优化网站搜索
  • 怎么学网站设计今日大新闻
  • 网站优化外链怎么做郑州百度推广托管
  • 开拓网站建设google官方入口
  • DW做网站入门步骤教学乐陵seo优化
  • 聊城找个人做网站国外市场网站推广公司
  • 做电影下载网站好站长网站提交
  • 怎么做公司内部网站网站内容编辑
  • 做视频网站可以自学吗google移动服务应用优化
  • 新疆外贸网站建设安全优化大师
  • 做网站网络公司无收入网站运营课程
  • java代码做网站app推广方法
  • 手机网站如何建站成都网站排名生客seo怎么样
  • 新手做代购网站扫货短视频推广引流方案
  • 网站如何建设与优化网络推广的含义
  • 推广计划ppt百度seo优
  • 做电影网站什么系统好长沙seo培训
  • 做自己的网站多少钱莆田网站建设优化
  • 网站制作 推荐新鸿儒企业培训机构哪家最好
  • 南昌装修网站建设阿里巴巴国际站
  • 专做女鞋批发的网站防晒霜营销软文
  • 汕头中英文网站推广网络营销的概念与特点
  • 政府采购网站的建设情况google store
  • 有什么网站可以接设计做seo广告平台
  • 广州比较好的网站建设公司关键词竞价排名
  • 项城网站设计share群组链接分享
  • pc 响应式网站模板百度seo优化是什么
  • 公司网站建设费用记什么科目杭州seo公司
  • 潍坊建设厅网站百度手机app下载并安装
  • 微信公众号小程序怎么创建手机优化什么意思