LeetCode 题解工作台
由斜杠划分区域
在由 1 x 1 方格组成的 n x n 网格 grid 中，每个 1 x 1 方块由 '/' 、 '\' 或空格构成。这些字符会将方块划分为一些共边的区域。 给定网格 grid 表示为一个字符串数组，返回 区域的数量 。 请注意，反斜杠字符是转义的，因此 '\' 用 '\\' 表示。 示例 1： …
6
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
class Solution: def regionsBySlashes(self, grid: List[str]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
在由 1 x 1 方格组成的 n x n 网格 grid 中，每个 1 x 1 方块由 '/'、'\' 或空格构成。这些字符会将方块划分为一些共边的区域。
给定网格 grid 表示为一个字符串数组，返回 区域的数量 。
请注意，反斜杠字符是转义的，因此 '\' 用 '\\' 表示。
示例 1：
输入：grid = [" /","/ "] 输出：2
示例 2：
输入：grid = [" /"," "] 输出：1
示例 3：
输入：grid = ["/\\","\\/"] 输出：5 解释：回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。
提示：
n == grid.length == grid[i].length1 <= n <= 30grid[i][j]是'/'、'\'、或' '
解题思路
方法一
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
def union(a, b):
pa, pb = find(a), find(b)
if pa != pb:
p[pa] = pb
nonlocal size
size -= 1
n = len(grid)
size = n * n * 4
p = list(range(size))
for i, row in enumerate(grid):
for j, v in enumerate(row):
k = i * n + j
if i < n - 1:
union(4 * k + 2, (k + n) * 4)
if j < n - 1:
union(4 * k + 1, (k + 1) * 4 + 3)
if v == '/':
union(4 * k, 4 * k + 3)
union(4 * k + 1, 4 * k + 2)
elif v == '\\':
union(4 * k, 4 * k + 1)
union(4 * k + 2, 4 * k + 3)
else:
union(4 * k, 4 * k + 1)
union(4 * k + 1, 4 * k + 2)
union(4 * k + 2, 4 * k + 3)
return size
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^2 \cdot \alpha(n^2)) due to union-find operations over n^2 subcells, and space complexity is O(n^2) to store subcell connectivity and visited states. |
| 空间 | O(n^2) |
面试官常问的追问
外企场景- question_mark
Clarifying whether '/' and '\' create 2 or more subregions per square.
- question_mark
Asking how DFS differs from union-find in this particular expanded grid approach.
- question_mark
Testing edge cases like all blanks or fully slashed grids to verify correct region counting.
常见陷阱
外企场景- error
Ignoring the need to split each square into 4 subcells, leading to undercounting regions.
- error
Confusing escaped backslashes in the input string with literal characters.
- error
Overlooking connections between neighboring squares' subcells, causing disconnected regions.
进阶变体
外企场景- arrow_right_alt
Counting regions in a hexagonal grid with slashes dividing hex cells.
- arrow_right_alt
Handling dynamic updates where slashes are added or removed and recalculating regions efficiently.
- arrow_right_alt
Determining largest region size instead of total number of regions.