第312题(2020-09-25)：给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

思路分析

这道题好就好在它题目不长，但是题干这通描述有可能会让一部分同学直接失去耐心——岛屿？水？“网格”？？？

啥啥啥？这都是啥？

其实，只要同学能够耐住性子读下去，就会发现所谓“网格”不过是二维数组，而“岛屿”和“水”这样的具体概念，题目也已经贴心地帮我们抽象为了“1”和“0”这样简单的数字。因此，我们拿到这道题，首先要做的就是把题目中这些干扰性的概念“翻译”成简单直接的算法语言：

已知一个二维数组，定义“相互连接的1”为一个块（这里的相互连接，意思就是1和1之间可以不经过0就相互抵达），求符合条件的块的数量。

翻译到这个程度之后，我们不难找出“相互连接”这个关键词作为我们做题的抓手，进而去形成一个初步的思路——若当前所在位置是1，从1出发，可以抵达的所有1都和它算作同一个岛屿。注意这里我把“所有”这个词标了粗体，已经读了25节算法小册的你，请和我一起大声喊出下面这句话：

看到“所有”，必须想到“枚举”！看到“枚举”，必须回忆起DFS和BFS！

喜欢递归的我，选择用 DFS 来做~~~

在明确了 DFS 的大方向之后，结合题意，我们可以提取出以下关键问题：

如何实现对不同岛屿的统计？
已经计算过的岛屿如何排除？

下面我一一回答这两个问题：

岛屿的统计思路：从起点出发，遵循“不撞水面（也就是0）不回头”的原则，枚举当前可以触及的所有1。当枚举无法继续进行时，说明当前这座岛屿被遍历完毕，记为一个。也就是说每完成一次 DFS，就累加一个岛屿。
避免重复计算的方法：每遍历过一个1，就把它置为0，后续再次路过时就会自动忽略它啦~~

回答完这俩问题，代码也算基本写完了（如果以上描述仍然无法帮你建立清晰的思路，不妨去代码注释里找一下答案~）：

编码实现

/**
 * @param {character[][]} grid
 * @return {number}
 */
// 入参是二维数组
const numIslands = function(grid) {
  const moveX = [0, 1, 0, -1]  
  const moveY = [1, 0, -1, 0]   
  // 处理二维数组的边界情况
  if(!grid || grid.length === 0 || grid[0].length === 0) {
      return 0
  }  
  // 初始化岛屿数量
  let count = 0  
  // 缓存二维数组的行数和列数
  let row = grid.length, column = grid[0].length  
  // 以行和列为线索，尝试“逐个”遍历二位数组中的坑位
  for(let i=0; i<row; i++) {
      for(let j=0; j<column; j++) {
          if(grid[i][j] === '1') {
              // 每遇到1，就进入dfs，探索岛屿边界
              dfs(grid, i, j)  
              // 每完成一个 dfs，就累加一个岛屿
              count++
          }
      }
  }
  return count

  // 编写探索岛屿边界的逻辑
  function dfs(grid, i, j) {  
      // 如果试图探索的范围已经越界，则return
      if(i<0 || i>=grid.length || j<0 || j>=grid[0].length || grid[i][j] === '0'){
          return  
      }   
      // 遍历过的坑位都置0，防止反复遍历
      grid[i][j] = '0'   
      // 遍历完当前的1，继续去寻找下一个1
      for(let k=0; k<4; k++) {
          dfs(grid, i+moveX[k], j+moveY[k])
      }
  }
}

qappleh / Interview

第312题(2020-09-25)：给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 #315

思路分析

编码实现