200.岛屿数量

链接：200.岛屿数量
难度：Medium
标签：深度优先搜索、广度优先搜索、并查集、数组、矩阵
简介：给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

题解 1 - javascript

• 编辑时间：2020-04-20
• 执行用时：296ms
• 内存消耗：45.2MB
• 编程语言：javascript
• 解法介绍：发现小岛后遍历周围是否有群岛，有群岛一并加入，再把小岛放入数组中，最后数组的数量即小岛个数。

const toSringIsland = (i, j) => `${i}-${j}`;
class Island {
  set = new Set();
  setIsland(i, j) {
    this.set.add(toSringIsland(i, j));
  }
  hasIsland(i, j) {
    return this.set.has(toSringIsland(i, j));
  }
}
/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  const col = grid.length;
  const islands = [];
  function dfs(i, j) {
    //   console.log("==============");
    //   console.log(i, j);
    //   console.log(grid[i][j]);
    if (grid[i][j] === '0') return;
    for (const item of islands) {
      if (item.hasIsland(i, j)) return;
    }
    const island = new Island();
    islands.push(island);
    const queue = [[i, j]];
    while (queue.length !== 0) {
      // console.log(queue);
      const [i, j] = queue.pop();
      // console.log("while i j", i, j);
      // console.log(queue);
      if (grid[i][j] === '0') continue;
      if (island.hasIsland(i, j)) continue;
      else island.setIsland(i, j);
      if (i < col - 1) queue.push([i + 1, j]);
      if (j < grid[i].length - 1) queue.push([i, j + 1]);
      if (i > 0) queue.push([i - 1, j]);
      if (j > 0) queue.push([i, j - 1]);
    }
    // console.log(islands);
  }
  for (let i = 0; i < col; i++) {
    const row = grid[i].length;
    for (let j = 0; j < row; j++) {
      dfs(i, j);
    }
  }
  return islands.length;
};

题解 2 - typescript

• 编辑时间：2021-04-30
• 执行用时：124ms
• 内存消耗：43MB
• 编程语言：typescript
• 解法介绍：并查集。

class UnionFind {
  elements: number[];
  constructor(public size: number) {
    this.elements = new Array(size).fill(0).map((_, i) => i);
  }
  same(v1: number, v2: number): boolean {
    return this.find(v1) === this.find(v2);
  }
  find(v: number): number {
    return v === this.elements[v] ? v : (this.elements[v] = this.find(this.elements[v]));
  }
  union(v1: number, v2: number): void {
    const e1 = this.find(v1);
    const e2 = this.find(v2);
    if (e1 !== e2) {
      this.elements[e1] = e2;
      this.size--;
    }
  }
}
function numIslands(grid: string[][]): number {
  let count = 0;
  const newGrid: number[][] = grid.map(row => row.map(col => (col === '0' ? -1 : count++)));
  const rowLen = grid.length;
  const colLen = grid[0].length;
  const uf = new UnionFind(count);
  for (let row = 0; row < rowLen; row++) {
    for (let col = 0; col < colLen; col++) {
      const num = newGrid[row][col];
      if (num === -1) continue;
      if (row > 0 && newGrid[row - 1][col] !== -1) uf.union(num, newGrid[row - 1][col]);
      if (col > 0 && newGrid[row][col - 1] !== -1) uf.union(num, newGrid[row][col - 1]);
      if (row < rowLen - 1 && newGrid[row + 1][col] !== -1) uf.union(num, newGrid[row + 1][col]);
      if (col < colLen - 1 && newGrid[row][col + 1] !== -1) uf.union(num, newGrid[row][col + 1]);
    }
  }
  return uf.size;
}