130. 被围绕的区域
https://leetcode-cn.com/problems/surrounded-regions/
解法一：dfs
两次遍历。第一次先遍历边界，dfs将所有与边界O相连的O置为‘-’。之后再遍历所有，将所有O变为X，所有’-‘变为O
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
n = len(board)
if n == 0:
return
m = len(board[0])
#对四条边界上的元素dfs遍历
for i in range(n):
self.dfs(i, 0, n, m, board)
self.dfs(i, m-1, n, m, board)
for j in range(m):
self.dfs(0, j, n, m, board)
self.dfs(n-1, j, n, m, board)
#遍历所有
for i in range(n):
for j in range(m):
#注意先后顺序不能颠倒
if board[i][j] == 'O':
board[i][j] = 'X'
if board[i][j] == '-':
board[i][j] = 'O'
def dfs(self, row, col, rows, cols, board):
if row >= 0 and row < rows and col >= 0 and col < cols and board[row][col] == 'O':
board[row][col] = '-' #特殊标记
#dfs遍历上下左右
self.dfs(row, col-1, rows, cols, board)
self.dfs(row, col+1, rows, cols, board)
self.dfs(row-1, col, rows, cols, board)
self.dfs(row+1, col, rows, cols, board) 解法二：并查集
被x包围的o一定不与外界（设为“虚拟节点”）连通，例如边界的o与外界连通。用并查集找出不与外界连通的o，然后置为x即可。
class UnionFind:
# 构造函数传入totalNodes为总节点数
def __init__(self, totalNodes):
# parents[i]表示i的根，初始i的根为其自身
self.parents = [i for i in range(totalNodes)]
# 连通分量数
self.count = totalNodes
# 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.
def union(self, node1, node2):
root1 = self.find(node1)
root2 = self.find(node2)
# 不连通才合并
if root1 != root2:
#注意：此处可优化（见优化二）
self.parents[root2] = root1
# 连通分量数减一
self.count -= 1
# 查找最终的根
def find(self, node):
#注意：此处可优化（见优化一）
node = self.parents[node]
return node
# 判断两个点是否连通
def isConnected(self, node1, node2):
return self.find(node1) == self.find(node2)
# 返回连通分量个数
def count(self):
return self.count
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if not board or len(board) == 0:
return
rows = len(board)
cols = len(board[0])
uf = UnionFind(rows * cols + 1) # 多出一个位置留给虚拟结点
dummyNode = rows * cols # 虚拟结点的一维坐标
# 为简化算法，将二维坐标转换为一维坐标
def node(i, j):
return i * cols + j
# 遍历所有点
for i in range(rows):
for j in range(cols):
if board[i][j] == 'O':
# 若是边界，则与虚拟结点合并
if i == 0 or i == rows - 1 or j == 0 or j == cols - 1:
uf.union(node(i, j), dummyNode)
else:
# 对上下左右的'O'结点进行合并
if i > 0 and board[i - 1][j] == 'O':
uf.union(node(i, j), node(i - 1, j))
if i < rows - 1 and board[i + 1][j] == 'O':
uf.union(node(i, j), node(i + 1, j))
if j > 0 and board[i][j - 1] == 'O':
uf.union(node(i, j), node(i, j - 1))
if j < cols - 1 and board[i][j + 1] == 'O':
uf.union(node(i, j), node(i, j + 1))
for i in range(rows):
for j in range(cols):
if board[i][j] == 'O':
# 与虚拟结点连通的点则保持'O'
if uf.isConnected(node(i, j), dummyNode):
board[i][j] = 'O'
else:
board[i][j] = 'X'优化
一、路径压缩
并查集的find函数可以改进
def find(self, node):
while self.parents[node] != node:
self.parents[node] = self.parents[self.parents[node]]
node = self.parents[node]
# 优化前
# node = self.parents[node]
return node如下图
调用 find 函数每次向树根遍历的同时，顺手将树高缩短了，最终所有树高都不会超过 3（union 的时候树高可能达到 3）。
二、平衡性优化
我们一开始就是简单粗暴的把 p 所在的树接到 q 所在的树的根节点下面，那么这里就可能出现「头重脚轻」的不平衡状况，比如下面这种局面
长此以往，树可能生长得很不平衡。我们希望小一些的树接到大一些的树下面，这样就能避免头重脚轻，更平衡一些。解决方法是额外使用一个 size 数组，记录每棵树包含的节点数，称为“重量”（size）
class UnionFind:
# 构造函数传入totalNodes为总节点数
def __init__(self, totalNodes):
# parents[i]表示i的根，初始i的根为其自身
self.parents = [i for i in range(totalNodes)]
# 连通分量数
self.count = totalNodes
# 树的“重量”
self.size = [1] * totalNodes
# 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.
def union(self, node1, node2):
root1 = self.find(node1)
root2 = self.find(node2)
# 不连通才合并
if root1 != root2:
# 小树合并到大树
if self.size[root1] > self.size[root2]:
self.parents[root2] = root1
self.size[root1] += self.size[root2]
else:
self.parents[root1] = root2
self.size[root2] += self.size[root1]
# 连通分量数减一
self.count -= 1
# 查找最终的根
def find(self, node):
while self.parents[node] != node:
self.parents[node] = self.parents[self.parents[node]]
node = self.parents[node]
return node
# 判断两个点是否连通
def isConnected(self, node1, node2):
return self.find(node1) == self.find(node2)
# 返回连通分量个数
def count(self):
return self.count最后更新于
