哈希算法题目：岛屿数量
字数 790 2025-10-29 11:31:55

哈希算法题目：岛屿数量

题目描述：
给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算网格中岛屿的数量。岛屿由水平或垂直相邻的陆地连接形成，假设网格四周被水包围。

示例：
输入：
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3（因为有3个互不相连的陆地群）

解题步骤：

  1. 问题分析
    岛屿的判定核心是连通性：相邻（上下左右）的 '1' 属于同一个岛屿。需要避免重复计数，因此访问过的陆地要标记。

  2. 哈希算法应用点
    虽然主要解法是DFS/BFS，但哈希表可用于优化：

    • 记录已访问的坐标（避免重复访问）
    • 序列化坐标作为唯一标识（例如将 (i, j) 转为字符串 "i,j"）

  3. 深度优先搜索（DFS）实现

    • 遍历网格每个点，遇到 '1' 且未访问过时：
      1. 岛屿计数 +1
      2. 递归访问其上下左右相邻的 '1'，并通过哈希表标记已访问
    • 递归终止条件：坐标越界、当前点为 '0' 或已访问

  4. 具体步骤
    a. 初始化哈希表 visited 和计数器 count = 0
    b. 遍历网格每个点 (i, j)：

    • 若 grid[i][j] == '1' 且 (i, j) 未在 visited 中：
      • 执行DFS：将当前点加入 visited，递归处理四个方向
      • 完成DFS后 count++
        c. 返回 count

  5. 复杂度分析

    • 时间复杂度：O(M×N)（每个点最多访问一次）
    • 空间复杂度：O(M×N)（哈希表存储和递归栈最深可能为整个网格）

关键技巧：

  • 使用哈希表快速判断坐标是否已访问
  • 通过方向数组 [(-1,0), (1,0), (0,-1), (0,1)] 简化相邻点遍历
哈希算法题目：岛屿数量 题目描述： 给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算网格中岛屿的数量。岛屿由水平或垂直相邻的陆地连接形成，假设网格四周被水包围。 示例： 输入： grid = [ [ "1","1","0","0","0" ], [ "1","1","0","0","0" ], [ "0","0","1","0","0" ], [ "0","0","0","1","1" ] ] 输出：3（因为有3个互不相连的陆地群） 解题步骤： 问题分析 岛屿的判定核心是 连通性 ：相邻（上下左右）的 '1' 属于同一个岛屿。需要避免重复计数，因此访问过的陆地要标记。 哈希算法应用点 虽然主要解法是DFS/BFS，但哈希表可用于优化： 记录已访问的坐标（避免重复访问） 序列化坐标作为唯一标识（例如将 (i, j) 转为字符串 "i,j"） 深度优先搜索（DFS）实现 遍历网格每个点，遇到 '1' 且未访问过时： 岛屿计数 +1 递归访问其上下左右相邻的 '1'，并通过哈希表标记已访问 递归终止条件：坐标越界、当前点为 '0' 或已访问 具体步骤 a. 初始化哈希表 visited 和计数器 count = 0 b. 遍历网格每个点 (i, j)： 若 grid[ i][ j] == '1' 且 (i, j) 未在 visited 中： 执行DFS：将当前点加入 visited ，递归处理四个方向 完成DFS后 count++ c. 返回 count 复杂度分析 时间复杂度：O(M×N)（每个点最多访问一次） 空间复杂度：O(M×N)（哈希表存储和递归栈最深可能为整个网格） 关键技巧： 使用哈希表快速判断坐标是否已访问 通过方向数组 [ (-1,0), (1,0), (0,-1), (0,1) ] 简化相邻点遍历