Union-Find算法应用 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：Union-Find算法应用

[shuowenwei]

this is elegant!

[shadow-mike]

👍

[Fan-sir]

good

[jswxwxf]

js 版 130. 被围绕的区域 不用 UF 的算法，感觉跟岛屿相关的问题很像。

var solve = function(board) {
  const m = board.length;
  const n = board[0].length;
  const DIRECTIONS = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  for (let col = 0; col < n; col++) {
    // 标记靠上边的棋子
    traverse(0, col);
    // 标记靠下边的棋子
    traverse(m - 1, col);
  }

  for (let row = 0; row < m; row++) {
    // 标记靠左边的棋子
    traverse(row, 0);
    // 标记靠右边的棋子
    traverse(row, n - 1);
  }

  // 剩下的都是被‘X’围绕的区域，置成‘X’
  for (let row = 0; row < m; row++) {
    for (let col = 0; col < n; col++) {
      if (board[row][col] === 'X') continue;
      if (board[row][col] === '#') {
        // 标记位置回
        board[row][col] = 'O';
        continue;
      }
      board[row][col] = 'X';
    }
  }

  return board;

  // DFS
  function traverse(row, col) {
    if (row < 0 || row >= m || col < 0 || col >= n) {
      // 超出边界
      return;
    }
    // 不需要标记或已经标记过
    if (['X', '#'].includes(board[row][col])) {
      return;
    }
    // 标记
    board[row][col] = '#';
    // 标记上下左右
    for (const d of DIRECTIONS) {
      const nextRow = row + d[0];
      const nextCol = col + d[1];
      traverse(nextRow, nextCol);
    }
  }
};

[jswxwxf]

js 版 990. 等式方程的可满足性

var equationsPossible = function(equations) {
  // 26 个英文字母
  const a = 'a'.charCodeAt(0);
  const uf = new UF(26);

  // 先让相等的字母形成连通分量
  for (const e of equations) {
    if (e[1] === '=') {
      const x = e[0];
      const y = e[3];
      uf.union(toNum(x), toNum(y));
    }
  }

  // 检查不等关系是否打破相等关系的连通性
  for (const e of equations) {
    if (e[1] === '!') {
      const x = e[0];
      const y = e[3];
      // 如果相等关系成立，就是逻辑冲突
      if (uf.connected(toNum(x), toNum(y))) {
        return false;
      }
    }
  }

  return true;

  function toNum(ch) {
    return ch.charCodeAt(0) - a;
  }
};