网站建设填空题,免费精品发布页怎么设计,重庆装修价格明细表,做网站制作挣钱吗[算法日志]图论刷题: 沉岛思想的运用
leetcode 695 岛屿最大面积
给你一个大小为 m x n 的二进制矩阵 grid .
岛屿 是由一些相邻的 1 (代表土地) 构成的组合, 这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻. 你可以假设 grid 的四个边缘都被 0#xff08…[算法日志]图论刷题: 沉岛思想的运用
leetcode 695 岛屿最大面积
给你一个大小为 m x n 的二进制矩阵 grid .
岛屿 是由一些相邻的 1 (代表土地) 构成的组合, 这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻. 你可以假设 grid 的四个边缘都被 0代表水包围着.
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积. 如果没有岛屿则返回面积为 0 .
本题依旧是一道较基础的图论搜索题采用DFS, BFS 或者后面将要学的并查集都可以解决本题, 但本题的重点在于引入一种算法思想.
沉岛思想
本题我们将DFS作为本题基础. 但不同的是, 我们将不再使用visited数组作为访问过的标记, 转而代之的是我将直接再直接在grid数组上进行修改.
当我们访问过一个岛屿节点1时, 将其改为0. 这种策略实际上与使用visited数组进行标记十分相似, 只不过没有额外分配一个数组, 转而在原本的数组上进行修改. 这其实是另一种算法思想(原地算法)的体现. 原地算法, 指在解决某种问题时利用原本数据空间, 而不额外分配空间. 采用这种算法策略, 在面对较大数据量时, 可以有效节约内存空间, 降低空间复杂度. 以下是本题的示例代码: const int dir[4][2] { {0, -1}, {1, 0}, {0, 1}, {-1, 0} };int DFS3(vectorvectorint g, int x, int y){if (x 0 || y 0 || x g[0].size() || y g.size() || !g[y][x])return 0;int result 1; g[y][x] 0;for (int i 0; i 4; i)result DFS3(g, x dir[i][0], y dir[i][1]);return result;}int maxAreaOfIsland(vectorvectorint grid) {if (grid.empty())return 0;int result 0;for (int i 0; i grid.size(); i){for (int j 0; j grid[0].size(); j){if (grid[i][j]){result max(result,DFS3(grid, j, i));}}}return result;}当然, 在本题中, 我们写的是函数接口, 所以不推荐对原数据的修改, 但这种算法思想依旧值得我们学习与效仿.
