网站搜索引擎拓客,网页拒绝访问怎么解决,网店推广的作用,龙岗教育在线官网问题描述
给定一个二维网格 grid#xff0c;其中1表示陆地#xff0c;0表示水域。网格中的格子水平和垂直方向相连#xff08;对角线不相连#xff09;。网格中恰好有一个岛屿#xff08;即一个或多个相连的陆地格子#xff09;#xff0c;需要计算这个岛屿的周长。 解…问题描述
给定一个二维网格 grid其中1表示陆地0表示水域。网格中的格子水平和垂直方向相连对角线不相连。网格中恰好有一个岛屿即一个或多个相连的陆地格子需要计算这个岛屿的周长。 解法一直接计数法迭代法
思路分析
这是最直观的解法遍历网格中的每个格子如果是陆地初始周长为4。然后检查其上下左右四个方向的相邻格子 每有一个相邻的陆地格子周长减1 边界情况自动处理边界外的格子视为水域
代码实现
class Solution {
public:int islandPerimeter(vectorvectorint grid) {int res 0;int m grid.size(), n grid[0].size();for(int i 0; i m; i) {for(int j 0; j n; j) {int add 4; // 方格初始周长if(grid[i][j] 1) {if(i - 1 0 grid[i - 1][j] 1) add--; // 上if(i 1 m grid[i 1][j] 1) add--; // 下if(j - 1 0 grid[i][j - 1] 1) add--; // 左if(j 1 n grid[i][j 1] 1) add--; // 右res add;}}}return res;}
};
复杂度分析 时间复杂度O(mn)其中m和n分别是网格的行数和列数 空间复杂度O(1)仅使用常数级别的额外空间
解法二数学计算法
思路分析
这种方法基于一个数学观察 每个陆地格子贡献4条边 每对相邻的陆地格子共享一条边会使总周长减少2条边
因此岛屿周长 陆地格子数 × 4 - 相邻边数 × 2
代码实现
class Solution {public int islandPerimeter(int[][] grid) {int landCount 0; // 陆地格子数量int adjacentCount 0; // 相邻边数量for (int r 0; r grid.length; r) {for (int c 0; c grid[0].length; c) {if (grid[r][c] 1) {landCount;// 只检查右侧和下侧避免重复计数if (c 1 grid[0].length grid[r][c 1] 1) {adjacentCount;}if (r 1 grid.length grid[r 1][c] 1) {adjacentCount;}}}}return landCount * 4 - adjacentCount * 2;}
}
复杂度分析 时间复杂度O(mn) 空间复杂度O(1)
解法三深度优先搜索DFS
思路分析
使用深度优先搜索遍历岛屿 当从陆地移动到边界或水域时周长增加1 使用标记避免重复访问将访问过的陆地标记为2 递归探索四个方向右、下、左、上
代码实现
class Solution {constexpr static int dx[4] {0, 1, 0, -1}; // 右、下、左、上constexpr static int dy[4] {1, 0, -1, 0};public:int dfs(int x, int y, vectorvectorint grid, int n, int m) {// 遇到边界或水域贡献1条边if (x 0 || x n || y 0 || y m || grid[x][y] 0) {return 1;}// 已访问过的陆地不贡献边if (grid[x][y] 2) {return 0;}grid[x][y] 2; // 标记为已访问int res 0;// 探索四个方向for (int i 0; i 4; i) {int tx x dx[i];int ty y dy[i];res dfs(tx, ty, grid, n, m);}return res;}int islandPerimeter(vectorvectorint grid) {int n grid.size(), m grid[0].size();int ans 0;for (int i 0; i n; i) {for (int j 0; j m; j) {if (grid[i][j] 1) {ans dfs(i, j, grid, n, m);}}}return ans;}
};
复杂度分析 时间复杂度O(mn)每个格子最多访问一次 空间复杂度O(mn)递归调用栈的深度在最坏情况下可能达到网格大小
总结与对比
方法优点缺点适用场景直接计数法直观易懂实现简单需要检查四个方向小规模网格数学计算法效率高仅需遍历一次需要理解数学原理所有规模网格深度优先搜索符合岛屿遍历的直觉可扩展性强需要递归可能栈溢出大规模连通岛屿或需要扩展功能
在实际应用中 对于简单场景数学计算法通常是最优选择高效且简洁 当需要扩展功能如计算多个岛屿时DFS更具扩展性 直接计数法则提供了最直观的实现参考
理解这三种解法的核心思想能够帮助我们在解决类似网格问题时灵活选择最合适的策略。
