一、先确定思路什么样的格子才算一个岛题目给一个由1陆地和0水组成的二维网格要求数出岛屿的数量。岛屿的定义是被水包围并且由水平或垂直方向上相邻的陆地连接而成。比如说textgrid [ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ]这里有两个岛左上角 4 个1连成一片右下角 2 个1连成一片。答案是2。那这道题咋想呢我们遍历每一个格子只要遇到一个1就说明发现了一个新岛。然后要把这个1以及和它连成一片的所有1全部标记掉免得后面重复计数。设置两个关键的东西遍历每个格子(i, j)遇到1就计数 1然后把整片岛淹掉标记为已访问但和「N 皇后」不一样这次不是一行一行放而是在二维网格上往四个方向扩散。所以得解决怎么把和当前陆地相连的整片陆地都找出来二、怎么把连成一片的陆地都标记掉假设当前在(i, j)遇到了一个1我们想把它上下左右所有相连的1都标记掉。有两种常见做法方法思路DFS从当前格子出发往四个方向递归遇到1就继续扩散BFS从当前格子出发用队列一层一层往外扩散两种都行DFS 写起来更短BFS 不怕递归太深。这里先讲 DFS。什么时候需要扩散从(i, j)出发往四个方向看上(i-1, j)下(i1, j)左(i, j-1)右(i, j1)只要满足没越界是1就继续从这个新格子扩散。怎么避免重复访问如果直接递归会死循环从(i,j)到(i1,j)又从(i1,j)回到(i,j)。所以需要一个标记。最简单的方法把访问过的1改成0。grid[i][j] 0;这样以后再遇到这个格子它就是水了不会再被当成陆地扩散也不会被重复计数。这一步就是淹岛发现一个岛就把整片岛淹掉。什么时候算扩散结束当四个方向都越界或者是0时当前格子的扩散就结束了递归自然返回。到这里整个思路就完整了遍历每个格子 (i, j) ↓ 是 1 │ ├── 否 → 跳过 │ └── 是 → 岛屿数 1 ↓ 从 (i, j) 开始 DFS ↓ 把当前格子改成 0 ↓ 往上下左右四个方向扩散 ↓ 遇到越界或 0 就停接下来就可以照着这个思路写代码了。三、完整代码DFSclass Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0) return 0; int m grid.length; int n grid[0].length; int count 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; // 发现一个新岛 dfs(grid, i, j); // 把整片岛淹掉 } } } return count; } private void dfs(char[][] grid, int i, int j) { int m grid.length; int n grid[0].length; // 越界或者是水直接返回 if (i 0 || i m || j 0 || j n || grid[i][j] 0) { return; } // 淹掉当前陆地 grid[i][j] 0; // 往四个方向扩散 dfs(grid, i - 1, j); // 上 dfs(grid, i 1, j); // 下 dfs(grid, i, j - 1); // 左 dfs(grid, i, j 1); // 右 } }四、完整代码BFS如果担心网格很大、递归太深导致栈溢出可以用 BFSclass Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0) return 0; int m grid.length; int n grid[0].length; int count 0; int[][] dirs {{-1,0},{1,0},{0,-1},{0,1}}; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; // BFS 淹岛 Queueint[] queue new LinkedList(); queue.offer(new int[]{i, j}); grid[i][j] 0; while (!queue.isEmpty()) { int[] cur queue.poll(); for (int[] d : dirs) { int ni cur[0] d[0]; int nj cur[1] d[1]; if (ni 0 ni m nj 0 nj n grid[ni][nj] 1) { grid[ni][nj] 0; queue.offer(new int[]{ni, nj}); } } } } } } return count; } }五、代码中的几个细节1. 为什么可以直接改gridgrid[i][j] 0;题目没有要求保留原网格所以直接改grid当 visited 用省掉一个boolean[][] visited的空间。如果面试官要求不能改输入那就得额外开一个visited数组boolean[][] visited new boolean[m][n];2. 为什么 DFS 里先判断越界再改值if (i 0 || i m || j 0 || j n || grid[i][j] 0) return; grid[i][j] 0;顺序很重要先判断能不能访问能访问才标记。如果先标记再判断越界的时候会数组越界报错。3. 为什么 BFS 里入队时就标记grid[ni][nj] 0; queue.offer(new int[]{ni, nj});入队前就标记成0避免同一个格子被多个邻居重复加入队列。如果出队时才标记队列里可能出现重复元素浪费空间和时间。4. DFS 和 BFS 怎么选DFSBFS代码更短稍长风险网格大时可能栈溢出用堆内存不怕深场景一般够用网格特别大时更稳面试时先写 DFS如果被问栈溢出再提 BFS。六、复杂度分析时间复杂度O(m × n)每个格子最多被访问一次访问完就变成0所以总共 O(m × n)。空间复杂度DFSO(m × n)最坏情况整片都是陆地递归深度达到 m × nBFSO(min(m, n))队列最多存一圈的格子七、最后复盘这道题和「N 皇后」都是在做搜索但它们的搜索方式完全不同。N 皇后岛屿数量搜索空间棋盘上放皇后二维网格上的陆地方向逐行放每行选一列上下左右四个方向扩散标记方式集合记录列和对角线把1改成0终止条件row n越界或遇到水目标找所有方案数连通块个数这次的思路其实就是先把题目里的要求转化成一个能计算的条件数岛屿数量 ↓ 每个 1 是一个岛的起点 ↓ 从这个 1 出发把相连的 1 全部标记 ↓ 标记完一片岛屿数 1 ↓ 继续遍历遇到未标记的 1 就是新岛所以做网格搜索题时我觉得可以先问三个问题怎么判断一个格子属于当前连通块怎么标记已访问避免重复怎么遍历所有起点把这三个问题想清楚再去写代码整个过程就会顺畅很多。