LeetCode 被围绕的区域题解

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[i1][j] O: uf.union(index, (i1) * 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][j1] 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。