由斜杠划分区域
难度:
标签:
题目描述
An n x n grid is composed of 1 x 1 squares where each 1 x 1 square consists of a '/', '\', or blank space ' '. These characters divide the square into contiguous regions.
Given the grid grid represented as a string array, return the number of regions.
Note that backslash characters are escaped, so a '\' is represented as '\\'.
Example 1:
Input: grid = [" /","/ "] Output: 2
Example 2:
Input: grid = [" /"," "] Output: 1
Example 3:
Input: grid = ["/\\","\\/"] Output: 5 Explanation: Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.
Constraints:
n == grid.length == grid[i].length1 <= n <= 30grid[i][j]is either'/','\', or' '.
代码结果
运行时间: 53 ms, 内存: 16.2 MB
/*
* 思路：
* 使用与Java解法相同的并查集思想，但利用Java Stream API来进行部分操作。
* 由于并查集的操作本质上是基于数组的操作，使用Stream处理会稍显复杂，这里演示部分Stream用法。
*/
import java.util.stream.IntStream;
class Solution {
public int regionsBySlashes(String[] grid) {
int n = grid.length;
int size = 4 * n * n;
UnionFind uf = new UnionFind(size);
IntStream.range(0, n).forEach(i -> {
IntStream.range(0, n).forEach(j -> {
int index = 4 * (i * n + j);
char c = grid[i].charAt(j);
if (c == '/') {
uf.union(index, index + 3);
uf.union(index + 1, index + 2);
} else if (c == '\\') {
uf.union(index, index + 1);
uf.union(index + 2, index + 3);
} else { // ' '
uf.union(index, index + 1);
uf.union(index + 1, index + 2);
uf.union(index + 2, index + 3);
}
if (j + 1 < n) {
uf.union(index + 1, index + 4 + 3);
}
if (i + 1 < n) {
uf.union(index + 2, index + 4 * n);
}
});
});
return uf.getCount();
}
class UnionFind {
int[] parent;
int count;
public UnionFind(int n) {
parent = IntStream.range(0, n).toArray();
count = n;
}
public int find(int x) {
if (x != parent[x]) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
count--;
}
}
public int getCount() {
return count;
}
}
}解释
方法:
该题解使用并查集（Union Find）算法来解决问题。思路是将每个小方格的四个角视为独立的点，通过斜线将这些点连接起来。如果两个点被同一条斜线连接，则它们属于同一个区域。为了处理边界情况，将网格的四条边界也视为被连接起来的。遍历整个网格，根据斜线的位置将点进行合并，如果发现两个点已经在同一个集合中，则说明形成了一个新的区域。
时间复杂度:
O(n^2α(n))
空间复杂度:
O(n^2)
代码细节讲解
🦆
如何理解这个问题中每个小方格的四个角被视为独立点，并通过斜线连接的处理方式？这种处理对解题有什么帮助？
▷🦆
并查集中的路径压缩技术是如何具体实现的？这种方法对提高算法性能有什么影响？
▷🦆
题解中提到，如果两个点已经在同一个集合中，则形成一个新的区域。这种情况是如何在代码中检测和处理的？
▷