算法训练营第55天|101孤岛的总面积|102沉没孤岛|103水流问题|104.建造最大岛屿

ops/2024/10/11 7:28:21/

101孤岛的总面积

我的思路:对每一片都求面积,同时递归时判断是否为孤岛。

改进思路:本题要求找到不靠边的陆地面积,那么我们只要从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋,然后再去重新遍历地图 统计此时还剩下的陆地就可以了。

102沉没孤岛

思路:与上题一致,唯一不同的就是周边靠陆地且相邻的陆地都变成2,之后陆地同时-1就可以沉没中间小岛。

103水流问题

原本思路:对每一个节点进行深度搜索,得到该节点所有可以到达的节点,就可以判断这个节点是否为结果节点。

原本思路问题:时间复杂度过高,会超时。

优化思路:逆向想法,从边路逆流而上,看能到达哪些地方。

出错点:没有分清行和列,导致数组访问越界。

104.建造最大岛屿

原本思路:遍历每一个节点,寻找最大岛。时间复杂度为四次方。

优化思路:首先遍历地图,得到每个岛屿,对其进行标号,用map对应面积,这样就可以通过受否连接其他岛屿直接加面积。

出错点:最大岛屿的初始值应该是原地图的最大岛屿,而不是0;

没有一片海被同一个岛屿包围的情况,被同一个岛屿包围只需要加一次,需要一个数组来记录。


http://www.ppmy.cn/ops/93067.html

相关文章

SPI通信协议

目录 一、SPI简介 二、寻址方式 三、通信过程 四、SPI设备时钟 五、极性和相位 5.1 CPOL0,CPHA0 5.2 CPOL0,CPHA1 5.3 CPOL1,CPHA0 5.4 CPOL1,CPHA1 🌈你好呀!我是 程序猿 🌌 2024感谢你…

怎样才算精通 Excel?

最强AI视频生成:小说文案智能分镜智能识别角色和场景批量Ai绘图自动配音添加音乐一键合成视频百万播放量https://aitools.jurilu.com/ 高赞回答很系统,但普通人这么学,没等精通先学废了! 4年前,我为了学数据分析&#…

无人机防炸宝典!!

四种易炸环境,你必须知道 避免在GPS信号不好的环境内飞行 在GPS信号弱或不稳定的环境中,无人机可能无法准确判断自身位置,导致飞行不稳定,甚至失控坠机。 注意细小物体 例如:树枝,电线等,这些细小物体往往…

Selenium + Python 自动化测试08(截图)

我们的目标是:按照这一套资料学习下来,大家可以独立完成自动化测试的任务。 上一篇我们讨论了滑块的操作方法,本篇文章我们讲述一下截图的操作方法。希望能够帮到爱学的小伙伴。 在实际的测试项目组中我们经常要截屏保存报错信息&#xff0c…

免费【2024】springboot 甘肃旅游工艺品商城的设计与实现

博主介绍:✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌ 技术范围:SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化…

8.8 哈希表简单 1 Two Sum 141 Linked List Cycle

1 Two Sum class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {//给的target是目标sum 要返回vector<int> res(2,0);是在num中找加数//首先假设每个输入都是由唯一的结果&#xff0c;而且不适用相同的元素两次一共有n*(n-1)种…

1.mysql-DDL-数据库操作

DDL-数据库操作定义语言 DML-数据库操作语言 DCL-数据库控制语言 DQL-数据库查询语言 DDL-数据库操作 DDL-数据库操作- 查询 查询所有数据 SHOW DATABASES;查询当前数据库 SELECT DATABASE();DDL-数据库操作- 创建 CREATE DATABSE [IF NOT EXISTS] 数据库名 [ DEFAULT CHA…

c++_游戏_狼人杀

思路主要包括以下几个部分&#xff1a; 角色分配&#xff1a;代码中通过随机数的方式给狼人、平民、预言家和法师等角色进行分配&#xff0c;保证每个角色的数量和身份的随机性。 游戏进行&#xff1a;根据狼人、平民、预言家和法师等角色的身份&#xff0c;游戏进行了夜晚和白…