上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution {
public:
int regionsBySlashes(vector<string>& grid) {
}
};
python3 解法, 执行用时: 260 ms, 内存消耗: 17.3 MB, 提交时间: 2022-11-16 17:06:57
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
m, n = len(grid), len(grid[0])
new_grid = [[0 for _ in range(3 * n)] for _ in range(3 * m)]
ans = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '/':
new_grid[3 * i][3 * j + 2] = 1
new_grid[3 * i + 1][3 * j + 1] = 1
new_grid[3 * i + 2][3 * j] = 1
if grid[i][j] == '\\':
new_grid[3 * i][3 * j] = 1
new_grid[3 * i + 1][3 * j + 1] = 1
new_grid[3 * i + 2][3 * j + 2] = 1
def dfs(i, j):
if 0 <= i < 3 * m and 0 <= j < 3 * n and new_grid[i][j] == 0:
new_grid[i][j] = 1
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
for i in range(3 * m):
for j in range(3 * n):
if new_grid[i][j] == 0:
ans += 1
dfs(i, j)
return ans
python3 解法, 执行用时: 220 ms, 内存消耗: 15.5 MB, 提交时间: 2022-11-16 17:06:12
class UF:
def __init__(self, M):
self.parent = {}
self.cnt = 0
# 初始化 parent，size 和 cnt
for i in range(M):
self.parent[i] = i
self.cnt += 1
def find(self, x):
if x != self.parent[x]:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
return x
def union(self, p, q):
if self.connected(p, q): return
leader_p = self.find(p)
leader_q = self.find(q)
self.parent[leader_p] = leader_q
self.cnt -= 1
def connected(self, p, q):
return self.find(p) == self.find(q)
class Solution:
def regionsBySlashes(self, grid):
n = len(grid)
N = n * n * 4
uf = UF(N)
def get_pos(row, col, i):
return (row * n + col) * 4 + i
for row in range(n):
for col in range(n):
v = grid[row][col]
if row > 0:
uf.union(get_pos(row - 1, col, 2), get_pos(row, col, 1))
if col > 0:
uf.union(get_pos(row, col - 1, 3), get_pos(row, col, 0))
if v == '/':
uf.union(get_pos(row, col, 0), get_pos(row, col, 1))
uf.union(get_pos(row, col, 2), get_pos(row, col, 3))
if v == '\\':
uf.union(get_pos(row, col, 1), get_pos(row, col, 3))
uf.union(get_pos(row, col, 0), get_pos(row, col, 2))
if v == ' ':
uf.union(get_pos(row, col, 0), get_pos(row, col, 1))
uf.union(get_pos(row, col, 1), get_pos(row, col, 2))
uf.union(get_pos(row, col, 2), get_pos(row, col, 3))
return uf.cnt
golang 解法, 执行用时: 4 ms, 内存消耗: 4.4 MB, 提交时间: 2022-11-16 17:02:57
type unionFind struct {
parent, size []int
setCount int // 当前连通分量数目
}
func newUnionFind(n int) *unionFind {
parent := make([]int, n)
size := make([]int, n)
for i := range parent {
parent[i] = i
size[i] = 1
}
return &unionFind{parent, size, n}
}
func (uf *unionFind) find(x int) int {
if uf.parent[x] != x {
uf.parent[x] = uf.find(uf.parent[x])
}
return uf.parent[x]
}
func (uf *unionFind) union(x, y int) {
fx, fy := uf.find(x), uf.find(y)
if fx == fy {
return
}
if uf.size[fx] < uf.size[fy] {
fx, fy = fy, fx
}
uf.size[fx] += uf.size[fy]
uf.parent[fy] = fx
uf.setCount--
}
func regionsBySlashes(grid []string) int {
n := len(grid)
uf := newUnionFind(4 * n * n)
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
idx := i*n + j
if i < n-1 {
bottom := idx + n
uf.union(idx*4+2, bottom*4)
}
if j < n-1 {
right := idx + 1
uf.union(idx*4+1, right*4+3)
}
if grid[i][j] == '/' {
uf.union(idx*4, idx*4+3)
uf.union(idx*4+1, idx*4+2)
} else if grid[i][j] == '\\' {
uf.union(idx*4, idx*4+1)
uf.union(idx*4+2, idx*4+3)
} else {
uf.union(idx*4, idx*4+1)
uf.union(idx*4+1, idx*4+2)
uf.union(idx*4+2, idx*4+3)
}
}
}
return uf.setCount
}
java 解法, 执行用时: 4 ms, 内存消耗: 41.1 MB, 提交时间: 2022-11-16 17:02:18
public class Solution {
public int regionsBySlashes(String[] grid) {
int N = grid.length;
int size = 4 * N * N;
UnionFind unionFind = new UnionFind(size);
for (int i = 0; i < N; i++) {
char[] row = grid[i].toCharArray();
for (int j = 0; j < N; j++) {
// 二维网格转换为一维表格，index 表示将单元格拆分成 4 个小三角形以后，编号为 0 的小三角形的在并查集中的下标
int index = 4 * (i * N + j);
char c = row[j];
// 单元格内合并
if (c == '/') {
// 合并 0、3，合并 1、2
unionFind.union(index, index + 3);
unionFind.union(index + 1, index + 2);
} else if (c == '\\') {
// 合并 0、1，合并 2、3
unionFind.union(index, index + 1);
unionFind.union(index + 2, index + 3);
} else {
unionFind.union(index, index + 1);
unionFind.union(index + 1, index + 2);
unionFind.union(index + 2, index + 3);
}
// 单元格间合并
// 向右合并：1（当前）、3（右一列）
if (j + 1 < N) {
unionFind.union(index + 1, 4 * (i * N + j + 1) + 3);
}
// 向下合并：2（当前）、0（下一行）
if (i + 1 < N) {
unionFind.union(index + 2, 4 * ((i + 1) * N + j));
}
}
}
return unionFind.getCount();
}
private class UnionFind {
private int[] parent;
private int count;
public int getCount() {
return count;
}
public UnionFind(int n) {
this.count = n;
this.parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
while (x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
parent[rootX] = rootY;
count--;
}
}
}
