Leetcode——岛屿的最大面积

1. 题目链接:695. 岛屿的最大面积

2. 题目描述:

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

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

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

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

示例 1:

img

输入: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

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j]01

3. 解法(递归):

3.1 算法思路:

  1. 遍历整个矩阵,每当遇到一块土地的时候,就用深度优先遍历或者宽度优先遍历将与这块土地相连的整个岛屿的面积计算出出来
  2. 然后在搜索得到的所有岛屿面积求一个最大值即可
  3. 在搜索过程中,为了防止搜到重复的土地:
    1. 可以开一个同等规模的布尔数组,标记以下这个位置是否已经被访问过
    2. 也可以将原始矩阵的1修改成0,但是这样的操作会修改原始矩阵

3.2 算法流程:

主函数内:

  1. 遍历整个数组,发现一块没有遍历到的土地之后,就用dfs将于这块土地相连的岛屿的面积求出来
  2. 然后将面积更新到最终结果ret

深度搜索dfs中:

  1. 能够进到dfs函数中,说明是一个没遍历到的位置
  2. 标记一下已经遍历过,设置一个变量count,记录最终的面积
  3. 上下左右遍历四个位置:如果找到一块没有遍历到的土地,就将这块土地相连的岛屿面积累加到count
  4. 循环结束后,count中存的就是这块岛屿的面积,返回即可

3.3 C++算法代码:

class Solution {bool vis[51][51]; // 访问标记数组,用于记录某个位置是否已经访问过int m, n; // 网格的行数和列数int dx[4] = {0, 0, 1, -1}; // x轴方向的偏移量int dy[4] = {1, -1, 0, 0}; // y轴方向的偏移量int count; // 当前岛屿的面积
public:// 计算给定网格中最大的岛屿面积int maxAreaOfIsland(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();int ret = 0; // 最大岛屿面积for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (!vis[i][j] && grid[i][j] == 1) { // 如果当前位置未被访问且为陆地count = 0; // 重置岛屿面积dfs(grid, i, j); // 进行深度优先搜索ret = max(ret, count); // 更新最大岛屿面积}}}return ret; // 返回最大岛屿面积}// 深度优先搜索函数,用于计算岛屿面积void dfs(vector<vector<int>>& grid, int i, int j) {count++; // 当前位置为陆地,岛屿面积加一vis[i][j] = true; // 标记当前位置已访问for (int k = 0; k < 4; k++) { // 遍历四个方向int x = i + dx[k], y = j + dy[k]; // 计算下一个位置的坐标if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1) { // 如果下一个位置在网格范围内且未被访问且为陆地dfs(grid, x, y); // 继续深度优先搜索}}}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/193708.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

[Mac软件]Adobe XD(Experience Design) v57.1.12.2一个功能强大的原型设计软件

Adobe XD是一个直观、强大的UI/UX开发工具&#xff0c;旨在设计、原型设计、用户之间共享材料&#xff0c;以及通过数字技术设计交互。Adobe XD为您提供开发网站、应用程序、语音界面、游戏界面、电子邮件模板等所需的一切。 无限制地创建 设计各种互动&#xff0c;创建看起来…

01序列 卡特兰数

解法&#xff1a; 将01序列置于坐标轴上&#xff0c;起始点为原点。0表示向右走&#xff0c;1表示向上走。这样就可以将前缀0的个数不少于1的个数就可以转换为路径上的点&#xff0c;横坐标大于纵坐标&#xff0c;也就是求合法路径个数。 注意题目mod的数是质数&#xff0c;所…

YOLOv5独家原创改进:最新原创WIoU_NMS改进点,改进有效可以直接当做自己的原创改进点来写,提升网络模型性能精度

💡该教程为属于《芒果书》📚系列,包含大量的原创首发改进方式, 所有文章都是全网首发原创改进内容🚀 💡本篇文章为YOLOv5独家原创改进:独家首发最新原创WIoU_NMS改进点,改进有效可以直接当做自己的原创改进点来写,提升网络模型性能精度。 💡对自己数据集改进有效…

开发知识点-Vue-Electron

Electron ElectronVue打包.exe桌面程序 ElectronVue打包.exe桌面程序 为了不报错 卸载以前的脚手架 npm uninstall -g vue-cli安装最新版脚手架 cnpm install -g vue/cli创建一个 vue 随便起个名 vue create electron-vue-example (随便起个名字electron-vue-example)进入 创建…

Node.js详解

一、是什么 Node.js 是一个开源与跨平台的 JavaScript 运行时环境 在浏览器外运行 V8 JavaScript 引擎&#xff08;Google Chrome 的内核&#xff09;&#xff0c;利用事件驱动、非阻塞和异步输入输出模型等技术提高性能 可以理解为 Node.js 就是一个服务器端的、非阻塞式I/…

关于Chrome中F12调试Console输入多行

在chrome 浏览器中使用console调试的时&#xff0c;如果想在console中输入多行代码&#xff0c;需要进行换行。 这时我们可以使用 [ Shift Enter ] 。也叫&#xff1a; 软回车。

C 语言实现 UDP

广播 发送广播信息&#xff0c;局域网中的客户端都可以接受该信息 #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <string.h> #include <arpa/inet.h>int main() {// 1.创建一个通信的socketint fd socket(PF_INET, …

S32DS踩坑日记五-bootloader跳转APP时触发DefaultISR

S32DS踩坑日记五-bootloader跳转APP时触发DefaultISR bootloader和APP由另一位同事开发过程中&#xff0c;被导师叫回去写论文了。 由于项目不急&#xff0c;接手后未作任何改动&#xff0c;后面硬件工程师手工焊了几块电路版&#xff0c;需要刷上程序测试电路板。然后就遇到了…

Java 通过POI快速导入带图片的excel并且图片不会丢失

## 通过POI快速导入带图片的excel并且图片不会丢失导入带图片的excel,这里也是研究了很久,在之前的博客中也有说明过,在项目使用过程中,发现很多时候导入响应很慢,而且每次导入图片都会丢失几张,所以又花了点时间研究修改了下,具体如下: 这边在导入时,通过自定义注解…

nginx启动命令

普通启动 切换到nginx安装目录的sbin目录下&#xff0c;执行&#xff1a;./nginx 通过配置文件启动 ./nginx -c /usr/local/nginx/conf/nginx.conf /usr/local/nginx/sbin/nginx -c /usr/local/nginx/conf/nginx.conf 其中-c是指定配置文件,而且配置文件路径必须指定绝对路…

MyBatis-Plus 系列

目录&#xff1a; 一、 Spring Boot 整合 MyBatis Plus 二、MyBatisPlus 多数据源配置 三、MybatisPlus —注解汇总 四、MyBatis Plus—CRUD 接口 五、MyBatis-Plus 条件构造器 六、MyBatis-Plus 代码生成器 MyBatis-Plus (opens new window)&#xff08;简称 MP&#xff09…

Dart 3.2 更新,Flutter Web 的未来越来越明朗

参考原文&#xff1a;https://medium.com/dartlang/dart-3-2-c8de8fe1b91f 本次跟随 Flutter 3.16 发布 的 Dart 3.2 &#xff0c;包含有&#xff1a;私有 final 字段的非空改进、新的 interop 改进、对 DevTools 中的扩展支持、以及对 Web 路线图的更新&#xff0c;包括对 Was…

解决requests库中session.verify参数失效的问题

在使用requests库进行HTTP请求时&#xff0c;如果在环境变量中设置了’REQUESTS_CA_BUNDLE’&#xff0c;并且在session对象中设置了verify参数为False&#xff0c;那么API请求会使用环境变量中的值而不是session对象中的值。这是因为在requests库中&#xff0c;当session对象中…

壹基金爱泽瑞金 安全家园物料配送忙

11月9日到10日&#xff0c;瑞金赋能公益陆续收到壹基金、阿里巴巴公益爱心网友捐赠的社区志愿者救援队队伍物资&#xff0c;马不停蹄地把物资配送到河背街社区、金都社区和沙洲坝镇等项目点&#xff0c;扎实稳妥推进项目有序执行。 在这次物资配送中&#xff0c;志愿者冒雨前行…

DC电源模块对效率有什么要求?

BOSHIDA DC电源模块对效率有什么要求&#xff1f; DC电源模块是现代科技中非常重要的组成部分&#xff0c;它是将交流电转换为直流电的装置&#xff0c;可以提供稳定的电源给各种设备和系统使用。效率是DC电源模块的一个关键性能指标&#xff0c;直接影响着模块的整体性能和效…

ssd202d-logo-cmd_bootlogo分析

cmd_bootlogo.c运行过程 common/autoboot.c:593: disp_logo(0); sprintf(cmd_str, "bootlogo %d 1 0 0 0", logo_id); do_display函数 获取对应结构体,里面有各种参数

Vim 从何而来?

Vim 编辑器的创造者、维护者和终身领导者 Bram Moolenaar 为了纪念这位杰出的荷兰程序员&#xff0c;我们今天来聊一聊 Vim 的历史。 Vim 无处不在。它被很多人使用。同时 Vim 可能是世界上 “最难用的软件之一” &#xff0c;但是又多次被程序员们评价为 最受欢迎的 代码编辑…

vite动态配置svg图标及其他方式集合

文章目录 前言使用vite-plugin-svg-icons动态配置安装插件引入图标下载新建组件svg-icon.vue使用 使用vue组件动态配置总结如有启发&#xff0c;可点赞收藏哟~ 前言 在配置化的情况下&#xff0c;图标配置也显得极为重要的 使用vite-plugin-svg-icons动态配置 参考vite-plugin…

软件系统集成指南

软件产品集成是将各种软件组件、模块和代码组装成最终可执行、可应用的软件产品的过程。这个过程涉及到将工作产品转化为产品的组装过程。在软件工程中&#xff0c;产品集成是一个重要的环节&#xff0c;通过持续性集成&#xff0c;将产品集成的过程常态化、自动化。做好产品集…

2023 年 数维杯(B题)国际大学生数学建模挑战赛 |数学建模完整代码+建模过程全解全析

当大家面临着复杂的数学建模问题时&#xff0c;你是否曾经感到茫然无措&#xff1f;作为2021年美国大学生数学建模比赛的O奖得主&#xff0c;我为大家提供了一套优秀的解题思路&#xff0c;让你轻松应对各种难题。 让我们来看看数维杯&#xff08;B题&#xff09;&#xff01; …