type
status
date
slug
summary
tags
category
icon
password
创建时间
Mar 16, 2025 02:48 AM
给你一个大小为
n x n
二进制矩阵 grid
。最多 只能将一格 0
变成 1
。返回执行此操作后,
grid
中最大的岛屿面积是多少?岛屿 由一组上、下、左、右四个方向相连的
1
形成。DFS
思路:
- 使用 DFS计算出每个岛屿的面积,并将其放入数组中。这样就将编号和面积对应起来了
- 遍历 grid 中每个为 0 的位置,使用哈希表记录该位置,向上下左右访问过的位置,
- 如果哈希表插入成功,说明相邻的是其他岛屿,可以增加面积
- 如果哈希表插入失败,说明相邻的是已经接触过的岛屿,不能增加面积
- 比较当前这个网格增加的面积与最大面积,取其中的最大值
参考 灵茶山艾府
收获
- 学习到哈希表的用途,在这里用的很巧妙,和 1. 两数之和 的思想相同,对已经访问过的内容进行存储。而且,在本题中利用哈希表插入函数的返回值,还起到判断的作用。
- 有很多标记网格已经访问的方法,可以将标记访问数组优化掉。
- 这种比较难的题,是将多种知识混合在一起,需要对各种算法知识都比较熟悉!!!!!