题目

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
输出：1
示例 2：

输入：grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
输出：3

题解一 dfs

var numIslands = function(grid) {function dfs(grid,i,j){//格式！// 递归终止条件if(i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j]==='0'){return  }grid[i][j]='0' // 走过的标记为0 两个中括号😂dfs(grid, i + 1, j)dfs(grid, i, j + 1)dfs(grid, i - 1, j)dfs(grid, i, j - 1)}let count=0for(let i=0;i<grid.length;i++){for(let j=0;j<grid[0].length;j++){if(grid[i][j]==='1'){dfs(grid,i,j)count++}}}return count
};

笔记：

1. void traverse(TreeNode root) {// 判断 base caseif (root == null) {return;}// 访问两个相邻结点：左子结点、右子结点traverse(root.left);traverse(root.right);
   }
   //dfs框架
   

2. 如何避免这样的重复遍历呢？答案是标记已经遍历过的格子。以岛屿问题为例，我们需要在所有值为 1 的陆地格子上做 DFS 遍历。每走过一个陆地格子，就把格子的值改为 2，这样当我们遇到 2 的时候，就知道这是遍历过的格子了。也就是说，每个格子可能取三个值：

   0 —— 海洋格子
   1 —— 陆地格子（未遍历过）
   2 —— 陆地格子（已遍历过）

3. 如果不把与它和同在一个岛的土地变成 0，则DFS遍历到它们时，会对一个岛重复计数

4. 怎么找出同处一岛的所有 1
   DFS，以当前 1 为入口
   DFS 做的事情：
   将当前的 1 变 0
   当前坐标的上下左右依次递归，同处一个岛的 1 都变 0
   dfs 出口：超出矩阵边界，或遇到 0。不用沉岛，直接返回

题解二 bfs

const numIslands = (grid) => {let count = 0let queue = []for (let i = 0; i < grid.length; i++) {for (let j = 0; j < grid[0].length; j++) {if (grid[i][j] === '1') {count++grid[i][j] = '0' // 做标记，避免重复遍历queue.push([i, j])turnZero(queue, grid)}}}return count
}
function turnZero(queue, grid) {const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]while (queue.length) {const cur = queue.shift()for (const dir of dirs) {const x = cur[0] + dir[0]const y = cur[1] + dir[1]if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] !== '1') {continue}grid[x][y] = '0'queue.push([x, y])}}
}

笔记：

1. 遇到 1 就计数 +1
   维护一个队列，遇到 1 就让它的坐标入列
   节点出列，并考察四个方向，如果是 1，将它转为 0，并将节点入列
   如果越界了或遇到 0 ，则跳过不用入列
   出列…入列…直到没有可以入列的节点，则当前岛屿的所有 1 都转 0 了
2. a这一排先进队列，a出队时孩子进队

题解三 并查集

class UnionFind {constructor(n) { //构造一个节点数为n的集合this.count = n //并查集总数this.parent = new Array(n)this.size = new Array(n)  // size数组记录着每棵树的重量for (let i = 0; i < n; i++) {this.parent[i] = i; // 自己是自己的parentthis.size[i] = 1;	//每个集合上节点的数量}}union(p, q) { //连通结点p和结点q, p和q都是索引let rootP = this.find(p);let rootQ = this.find(q);if (rootP === rootQ) return// 元素数量小的接到数量多的下面，这样比较平衡if (this.size[rootP] > this.size[rootQ]) {this.parent[rootQ] = rootP;this.size[rootP] += this.size[rootQ];} else {this.parent[rootP] = rootQ;this.size[rootQ] += this.size[rootP];}this.count--;}isConnected(p, q) { //判断p,q是否连通return this.find(p) === this.find(q)}find(x) { //找到x结点的rootwhile (this.parent[x] != x) {// 进行路径压缩this.parent[x] = this.parent[this.parent[x]];x = this.parent[x];}return x;}getCount() { //返回子集个数return this.count;}}var numIslands = function (grid) {let m = grid.lengthif (m === 0) return 0let n = grid[0].lengthconst dummy = -1const dirs = [[1, 0], [0, 1]]//方向数组 向右 向下const uf = new UnionFind(m * n)for (let x = 0; x < m; x++) {for (let y = 0; y < n; y++)if (grid[x][y] === '0') {//如果网格是0，则和dummy合并uf.union(n * x + y, dummy) }else if (grid[x][y] === '1') {//如果网格是1，则向右 向下尝试for (let d of dirs) {let r = x + d[0]let c = y + d[1]if (r >= m || c >= n) continue //坐标合法性if (grid[r][c] === '1') { //当前网格的右边 下面如果是1，则和当前网格合并uf.union(n * x + y, n * r + c)}}}}return uf.getCount()  //返回并查集的个数减一就行
};

笔记：

1. 所有的0固定合并，最后count减一个