并查集

思想

属于一种特殊的数据结构，在解决连通域问题上有着不错的性能。

三个组件

1. 维护一个数组 let parents = []，存放当前节点的父节点，根节点的父节点是其本身

2. 查询一个节点的根节点是哪个节点

   let parents = []
   function find(root){
       let temp, son = root;
       while(root !== parents[root]){
           root = parents[root];
       }
       while(son !== root){    //路径压缩，其实就是个扁平化处理的过程
           temp = parents[son];
           parents[son] = root;
           son = temp;
       }
       return root;
   }
   
   //递归版
   function find(root){
       if(root !== parents[root]) parents[root] = find(parents[root]);
       return parents[root];
   }

3. 合并两个连通域

   function join(x,y){
       x = find(x);
       y = find(y);
           if(x !== y){
           parents[x] = y;
       }
   }

题目

岛屿数量

思路

1. 写三大组件，初始化 parents 时将其键值对应
2. 判定当前节点四周是否存在陆地，如果有就将它们连接起来，如果没有就将当前节点的父节点置反
3. 求出 parents 数组中键和值依然相等的数目（即为连通域的数目）

答案

function numIslands(grid: string[][]): number {
  const row = grid.length;
  if (row === 0) return 0;

  const col = grid[0].length;
  const parents: number[] = [];

  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      parents[i * col + j] = i * col + j;
    }
  }

  function find(root: number): number {
    if (root !== parents[root]) parents[root] = find(parents[root]);
    return parents[root];
  }

  function union(x: number, y: number): void {
    x = find(x);
    y = find(y);
    if (x !== y) {
      parents[x] = y;
    }
  }

  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (grid[i][j] === "1") {
        i < row - 1 &&
          grid[i + 1][j] === "1" &&
          union((i + 1) * col + j, i * col + j);
        j < col - 1 &&
          grid[i][j + 1] === "1" &&
          union(i * col + j + 1, i * col + j);
      } else {
        parents[i * col + j] = -parents[i * col + j];
      }
    }
  }
  return parents.filter((value, key) => key === value && Object.is(key, value))
    .length;
}

DFS 解法

function numIslands(grid: string[][]): number {
  let res = 0
  const rows = grid.length
  if(!rows) return 0
  
  const cols = grid[0].length
  
  function helper(i: number, j: number): void {
        if (i < 0 || j < 0 || i > rows - 1 || j > cols - 1 || grid[i][j] === '0') return
    grid[i][j] = '0'
    helper(i + 1, j)
    helper(i, j + 1)
    helper(i - 1, j)
    helper(i, j - 1)
  }
  
  for(let i = 0; i < rows; i++) {
    for(let j = 0; j < cols; j++) {
      if(grid[i][j] === '1') {
        helper(i, j)
        res++
      }
    }
  }
  
  return res
}

被围绕的区域

思路

1. 写三大组件
2. 将 0 节点划分为内部节点和边界节点，引入一个虚拟边界 root 节点
3. 判定 0 节点是否为内部节点，如果是则替换为 x

答案

function solve(board: string[][]): void {
  const row = board.length;
  if (row === 0) return;

  const col = board[0].length;
  const parents: number[] = [];
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      parents[i * col + j] = i * col + j;
    }
  }
  function find(root: number): number {
    if (root !== parents[root]) parents[root] = find(parents[root]);
    return parents[root];
  }

  function union(x: number, y: number): void {
    x = find(x);
    y = find(y);
    if (x !== y) {
      parents[x] = y;
    }
  }
  function isConnected(x: number, y: number): boolean {
    return find(x) === find(y);
  }

  let virtualArea = row * col + 1;

  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (board[i][j] === "O") {
        if (i === 0 || i === row - 1 || j === 0 || j === col - 1) {
          union(i * col + j, virtualArea);
        } else {
          i > 0 &&
            board[i - 1][j] === "O" &&
            union(i * col + j, (i - 1) * col + j);
          i < row - 1 &&
            board[i + 1][j] === "O" &&
            union(i * col + j, (i + 1) * col + j);
          j > 0 &&
            board[i][j - 1] === "O" &&
            union(i * col + j, i * col + j - 1);
          j < col - 1 &&
            board[i][j + 1] === "O" &&
            union(i * col + j, i * col + j + 1);
        }
      }
    }
  }
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (board[i][j] === "O" && !isConnected(i * col + j, virtualArea)) {
        board[i][j] = "X";
      }
    }
  }
}