前端随笔 FE-Essay

# 并查集

# 思想

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

# 三个组件

  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;
    }
}

# 题目

# 岛屿数量 (opens new window)

# 思路

  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
}

# 被围绕的区域 (opens new window)

# 思路

  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";
      }
    }
  }
}

← 排序算法.md →