并查集。。针对这道题。。速度和性能并不高
class Solution {
class MyUnionFind {
var parents = [Int]()
var ranks : [Int]
init(_ capacity:Int){
ranks = Array.init(repeating: 1, count: capacity)
for i in 0..<capacity {
parents.append(i)
}
}
func find(_ v:Int)-> Int{
var temp = v
//路径减半
while parents[temp] != temp {
parents[temp] = parents[parents[temp]]
temp = parents[temp]
}
return temp
}
func union(_ v1:Int,_ v2:Int){
let p1 = find(v1)
let p2 = find(v2)
if p1 == p2 {
return
}
let r1 = ranks[p1]
let r2 = ranks[p2]
if r1 < r2 {
parents[p1] = p2
}else if r1 > r2 {
parents[p2] = p1
}else {
parents[p1] = p2
ranks[p2] += 1
}
}
func isSame(_ v1:Int,_ v2:Int)-> Bool{
return find(v1) == find(v2)
}
}
func solve(_ board: inout [[Character]]) {
let row = board.count
let col = board.first!.count
//初始化并查集
let uf = MyUnionFind(row * col + 1)
//先把边界的和虚拟的节点相连，其他的等于O的连接起来
for i in 0..<row {
for j in 0..<col {
let ch = board[i][j]
//查找和边界相连的
if j == col - 1 || i == 0 || j == 0 || i == row - 1 {
if ch == "O" {
uf.union(i * col + j, row * col)
}
}else {
if ch == "O" {
//右边的
if j + 1 < col {
if board[i][j + 1] == "O" {
uf.union(i * col + j, i * col + j + 1)
}
}
//往左
if j - 1 >= 0 {
if board[i][j - 1] == "O" {
uf.union(i * col + j, i * col + j - 1)
}
}
//往下
if i + 1 < row {
if board[i + 1][j] == "O" {
uf.union((i + 1) * col + j, i * col + j)
}
}
//往上
if i - 1 >= 0 {
if board[i - 1][j] == "O" {
uf.union((i - 1) * col + j, i * col + j)
}
}
}
}
}
}
for i in 0..<row {
for j in 0..<col {
if board[i][j] == "O" {
if j == col - 1 || i == 0 || j == 0 || i == row - 1 {
continue
}
if !uf.isSame(i * col + j,row * col) {
board[i][j] = "X"
}
}
}
}
}
}
然后dfs
func solve(_ board: inout [[Character]]) {
let row = board.count
let col = board.first!.count
//四条边
for i in 0..<row {
dfs(&board,row,col,i,0)
dfs(&board,row,col,i,col - 1)
}
for j in 0..<col {
dfs(&board,row,col,0,j)
dfs(&board,row,col,row - 1,j)
}
for i in 0..<row {
for j in 0..<col{
let ch = board[i][j]
if ch == "S" {
board[i][j] = "O"
}else if ch == "O" {
board[i][j] = "X"
}
}
}
}
func dfs(_ board:inout [[Character]],_ row:Int,_ col:Int,_ i:Int, _ j:Int) {
if i < 0 || j < 0 || i == row || j == col {
return
}
if board[i][j] != "O" {
return
}
board[i][j] = "S"
//往右
dfs(&board,row,col,i,j + 1)
//往左
dfs(&board,row,col,i,j - 1)
//往上
dfs(&board,row,col,i - 1,j)
//往下
dfs(&board,row,col,i + 1,j)
}
网友评论