企业官网建设流程全解析

LeetCode 被围绕的区域题解

题目描述

给定一个二维矩阵，包含 'X' 和 'O'。将所有被 'X' 包围的 'O' 区域替换为 'X'。

示例：

输入：

XXXX XOOX XXOX XOXX

输出：

XXXX XOOX XXOX XOXX

解题思路

方法：并查集

思路：

• 使用并查集来解决这个问题。
• 首先将所有边界的 'O' 与一个虚拟节点连接。
• 然后遍历矩阵，将相邻的 'O' 合并。
• 最后遍历矩阵，如果 'O' 没有与虚拟节点连接，则替换为 'X'。

复杂度分析：

• 时间复杂度：O(m * n)。
• 空间复杂度：O(m * n)。

代码实现

class UnionFind: def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): px, py = self.find(x), self.find(y) if px == py: return if self.rank[px] < self.rank[py]: px, py = py, px self.parent[py] = px if self.rank[px] == self.rank[py]: self.rank[px] += 1 def solve(board): if not board: return m, n = len(board), len(board[0]) uf = UnionFind(m * n + 1) dummy = m * n for i in range(m): for j in range(n): if board[i][j] == 'O': index = i * n + j if i == 0 or i == m - 1 or j == 0 or j == n - 1: uf.union(index, dummy) else: if i > 0 and board[i-1][j] == 'O': uf.union(index, (i-1) * n + j) if i < m - 1 and board[i+1][j] == 'O': uf.union(index, (i+1) * n + j) if j > 0 and board[i][j-1] == 'O': uf.union(index, i * n + j - 1) if j < n - 1 and board[i][j+1] == 'O': uf.union(index, i * n + j + 1) for i in range(m): for j in range(n): if board[i][j] == 'O' and uf.find(i * n + j) != uf.find(dummy): board[i][j] = 'X' # 测试 def test_solve(): board = [['X', 'X', 'X', 'X'], ['X', 'O', 'O', 'X'], ['X', 'X', 'O', 'X'], ['X', 'O', 'X', 'X']] solve(board) print(board) if __name__ == "__main__": test_solve()

总结

被围绕的区域是并查集的典型应用，将边界的 'O' 与虚拟节点连接，最后替换未被连接的 'O'。