标签: 深度优先搜索 广度优先搜索 并查集 哈希表 哈希函数
难度: Hard
Submission
运行时间: 130 ms
内存: 17.9 MB
class Solution:
def numDistinctIslands2(self, grid: List[List[int]]) -> int:
shapes = set()
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] <= 0:
continue
plots = []
todo = [(i, j)]
grid[i][j] = -grid[i][j]
while todo:
x, y = todo.pop()
plots.append((x - i, y - j))
for c, d in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
if 0 <= c < m and 0 <= d < n and grid[c][d] > 0:
todo.append((c, d))
grid[c][d] = -grid[c][d]
shapes.add(tuple(plots))
rf_shapes = set()
for shape in shapes:
min_x = min(s[0] for s in shape)
min_y = min(s[1] for s in shape)
max_x = max(s[0] for s in shape)
max_y = max(s[1] for s in shape)
max_x -= min_x
max_y -= min_y
tmp = [[] for _ in range(8)]
for x, y in shape:
x -= min_x
y -= min_y
tmp[0].append((x, y))
tmp[1].append((max_y - y, x))
tmp[2].append((max_y - y, max_x - x))
tmp[3].append((max_x - x, max_y - y))
tmp[4].append((x, max_y - y))
tmp[5].append((max_x - x, y))
tmp[6].append((y, max_x - x))
tmp[7].append((y, x))
for i, s in enumerate(tmp):
tmp[i] = tuple(sorted(s))
if any(s in rf_shapes for s in tmp):
continue
rf_shapes.add(tmp[0])
return len(rf_shapes)
Explain
这个题解的思路是先用 DFS 或 BFS 找出每个岛屿的形状，并将岛屿的形状表示为相对于左上角的坐标偏移量。然后对每个形状进行 8 种变换（旋转和翻转），将变换后的形状进行比较，去除重复的岛屿形状，最终得到不同岛屿的数量。
时间复杂度: O(mn * log(mn))
空间复杂度: O(mn)
class Solution:
def numDistinctIslands2(self, grid: List[List[int]]) -> int:
shapes = set()
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] <= 0:
continue
plots = []
todo = [(i, j)]
grid[i][j] = -grid[i][j] # 标记访问过的岛屿
while todo:
x, y = todo.pop()
plots.append((x - i, y - j)) # 记录相对于左上角的坐标偏移量
for c, d in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
if 0 <= c < m and 0 <= d < n and grid[c][d] > 0:
todo.append((c, d))
grid[c][d] = -grid[c][d] # 标记访问过的岛屿
shapes.add(tuple(plots)) # 将岛屿的形状添加到集合中
rf_shapes = set()
for shape in shapes:
min_x = min(s[0] for s in shape)
min_y = min(s[1] for s in shape)
max_x = max(s[0] for s in shape)
max_y = max(s[1] for s in shape)
max_x -= min_x
max_y -= min_y
tmp = [[] for _ in range(8)] # 存储 8 种变换后的形状
for x, y in shape:
x -= min_x
y -= min_y
tmp[0].append((x, y)) # 原始形状
tmp[1].append((max_y - y, x)) # 顺时针旋转 90 度
tmp[2].append((max_y - y, max_x - x)) # 顺时针旋转 180 度
tmp[3].append((max_x - x, max_y - y)) # 顺时针旋转 270 度
tmp[4].append((x, max_y - y)) # 水平翻转
tmp[5].append((max_x - x, y)) # 垂直翻转
tmp[6].append((y, max_x - x)) # 主对角线翻转
tmp[7].append((y, x)) # 副对角线翻转
for i, s in enumerate(tmp):
tmp[i] = tuple(sorted(s)) # 对每种变换后的形状进行排序
if any(s in rf_shapes for s in tmp):
continue
rf_shapes.add(tmp[0]) # 将变换后的形状添加到集合中
return len(rf_shapes) # 返回不同岛屿的数量
Explore
题解中的8种变换包括岛屿形状的旋转和翻转操作，具体包括：1) 原始形状；2) 顺时针旋转90度；3) 顺时针旋转180度；4) 顺时针旋转270度；5) 水平翻转；6) 垂直翻转；7) 主对角线翻转（即沿左上到右下的对角线翻转）；8) 副对角线翻转（即沿右上到左下的对角线翻转）。实现这些变换的关键在于坐标的变换规则：例如，顺时针旋转90度将坐标(x, y)变换为(y, max_x - x)，其中max_x是形状中x坐标的最大值。水平翻转则将每个点的y坐标映射到max_y - y，其中max_y是形状中y坐标的最大值。通过这样的坐标变换，可以生成岛屿的所有可能的变换形态。
为了确保能够正确比较并去除重复的岛屿形状，题解中采用了两个关键步骤：首先，对每种变换后的形状进行排序，以确保形状的坐标列表是有序的，这使得相同形状的不同表示（例如旋转或翻转后）能够被归一化到相同的序列。其次，使用集合(set)存储这些排序后的形状，利用集合的特性来自动去除重复项（因为集合不允许存储重复元素）。这样，只要有任一变换形态已存在于集合中，就不再添加新的变换形态，从而实现了重复形状的去除。
对岛屿形状的坐标进行排序是为了确保所有变换后的形状可以有一个统一的表示方式，即无论形状如何旋转或翻转，其坐标序列在排序后都应相同。这样做的目的是消除由于坐标顺序不同而导致的重复存储问题。例如，不同的变换可能导致形状看起来不同，但实际上是同一个形状的不同表达。通过排序，可以将这些形状归一化，使得相同的形状具有相同的坐标序列，从而便于比较和去重。
使用集合(set)来存储岛屿形状是因为集合具有唯一性的特点，即它不允许存储重复的元素。这一特性非常适合用于去除重复的岛屿形状，确保每个形状只被计算一次。如果使用列表(list) 或其他数据结构，则需要手动管理重复数据的问题，这不仅增加了编程的复杂性，也可能导致效率低下。集合在内部通过哈希表实现，具有高效的查找、插入和删除操作，这使得它非常适合本题的需求。