LeetCode 694 Number of Distinct Islands 全解：坐标归一化与三种形状哈希去重方案-平芜编程栈

LeetCode 694 Number of Distinct Islands 全解：坐标归一化与三种形状哈希去重方案

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本篇文章基于当前仓库的题解文档 number-of-distinct-islands.md，系统讲解 LeetCode 694《Number of Distinct Islands》的完整解题思路与多语言实现。你会掌握"如何为二维网格中的岛屿形状生成与位置无关的唯一签名"，并对比三种从 O(M²·N²) 暴力比较到 O(M·N) 哈希去重的递进方案，可直接在面试与工程中复用。文中所引用的网格 DFS 遍历模式，可对照仓库中的岛屿数量实现与封闭岛屿实现印证。

问题本质：比"数岛屿"多一个形状维度

LeetCode 200《Number of Islands》只统计连通块个数，而 694 要求进一步区分形状：两个岛屿只要可以通过平移（上下左右整体位移）完全重合，就被视为同一个岛屿，即使它们出现在网格的不同位置。因此解题的核心挑战是：

如何为每个岛屿生成一个与位置无关、与形状一一对应的签名（signature）。

这与仓库中其他岛屿系列题解属于同一 DFS 遍历框架（可参考岛屿数量、最大岛屿面积、岛屿周长、统计子岛屿），区别仅在于"拿到岛屿后如何描述它"。

前置知识（Prerequisites）

在动手写代码前，需要具备以下四项基础能力：

图遍历 DFS：能够探索 2D 网格中属于同一岛屿的所有格子，边界检查与去重标记是基本功；
坐标归一化（Coordinate normalization）：把岛屿中每个格子相对于某个原点（通常是首次发现的格子）记录偏移量，从而把形状从具体坐标中"剥离"出来；
哈希（Hashing）：使用集合与可哈希数据结构存储岛屿的唯一签名；
路径编码（Path encoding）：记录 DFS 的遍历方向序列，用路径本身作为形状的签名。

下面介绍的三种解法，正是围绕"如何构造签名"展开的递进。

方案一：暴力比较（Brute Force）

直觉

两个岛屿形状相同，当且仅当一个岛屿可以通过平移与另一个完全重合。因此可以先对每个岛屿做坐标归一化：把每个格子记录为相对于岛屿原点（首个发现的格子）的偏移(row - row_origin, col - col_origin)。归一化之后，形状相同的岛屿会得到完全相同的坐标集合，与它们位于网格的哪个位置无关。之后把新发现的岛屿与所有已存储的"唯一岛屿"逐一比较，即可判断是否重复。

算法步骤

用dfs探索每个岛屿，把格子记录为相对起点的偏移坐标；
对每个新发现的岛屿，与所有已存储的唯一岛屿逐一比较：
- 若大小（格子数）不同，则必然不同；
- 否则逐格比较偏移坐标；
若与所有已存岛屿都不相同，则加入唯一岛屿列表；
返回唯一岛屿的数量。

多语言实现

::tabs-start

class Solution: def numDistinctIslands(self, grid: List[List[int]]) -> int: def current_island_is_unique(): for other_island in unique_islands: if len(other_island) != len(current_island): continue for cell_1, cell_2 in zip(current_island, other_island): if cell_1 != cell_2: break else: return False return True # Do a DFS to find all cells in the current island. def dfs(row, col): if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]): return if (row, col) in seen or not grid[row][col]: return seen.add((row, col)) current_island.append((row - row_origin, col - col_origin)) dfs(row + 1, col) dfs(row - 1, col) dfs(row, col + 1) dfs(row, col - 1) # Repeatedly start DFS's as long as there are islands remaining. seen = set() unique_islands = [] for row in range(len(grid)): for col in range(len(grid[0])): current_island = [] row_origin = row col_origin = col dfs(row, col) if not current_island or not current_island_is_unique(): continue unique_islands.append(current_island) print(unique_islands) return len(unique_islands)

class Solution { private List<List<int[]>> uniqueIslands = new ArrayList<>(); // All known unique islands. private List<int[]> currentIsland = new ArrayList<>(); // Current Island private int[][] grid; // Input grid private boolean[][] seen; // Cells that have been explored. public int numDistinctIslands(int[][] grid) { this.grid = grid; this.seen = new boolean[grid.length][grid[0].length]; for (int row = 0; row < grid.length; row++) { for (int col = 0; col < grid[0].length; col++) { dfs(row, col); if (currentIsland.isEmpty()) { continue; } // Translate the island we just found to the top left. int minCol = grid[0].length - 1; for (int i = 0; i < currentIsland.size(); i++) { minCol = Math.min(minCol, currentIsland.get(i)[1]); } for (int[] cell : currentIsland) { cell[0] -= row; cell[1] -= minCol; } // If this island is unique, add it to the list. if (currentIslandUnique()) { uniqueIslands.add(currentIsland); } currentIsland = new ArrayList<>(); } } return uniqueIslands.size(); } private void dfs(int row, int col) { if (row < 0 || col < 0 || row >= grid.length || col >= grid[0].length) return; if (seen[row][col] || grid[row][col] == 0) return; seen[row][col] = true; currentIsland.add(new int[]{row, col}); dfs(row + 1, col); dfs(row - 1, col); dfs(row, col + 1); dfs(row, col - 1); } private boolean currentIslandUnique() { for (List<int[]> otherIsland : uniqueIslands) { if (currentIsland.size() != otherIsland.size()) { continue; } if (equalIslands(currentIsland, otherIsland)) { return false; } } return true; } private boolean equalIslands(List<int[]> island1, List<int[]> island2) { for (int i = 0; i < island1.size(); i++) { if (island1.get(i)[0] != island2.get(i)[0] || island1.get(i)[1] != island2.get(i)[1]) { return false; } } return true; } }

impl Solution { pub fn num_distinct_islands(grid: Vec<Vec<i32>>) -> i32 { let rows = grid.len(); let cols = grid[0].len(); let mut seen = vec![vec![false; cols]; rows]; let mut unique_islands: Vec<Vec<(i32, i32)>> = Vec::new(); fn dfs( grid: &[Vec<i32>], seen: &mut Vec<Vec<bool>>, r: i32, c: i32, island: &mut Vec<(i32, i32)>, ) { if r < 0 || c < 0 || r >= grid.len() as i32 || c >= grid[0].len() as i32 { return; } let (ru, cu) = (r as usize, c as usize); if seen[ru][cu] || grid[ru][cu] == 0 { return; } seen[ru][cu] = true; island.push((r, c)); dfs(grid, seen, r + 1, c, island); dfs(grid, seen, r - 1, c, island); dfs(grid, seen, r, c + 1, island); dfs(grid, seen, r, c - 1, island); } for row in 0..rows { for col in 0..cols { let mut current_island = Vec::new(); dfs(&grid, &mut seen, row as i32, col as i32, &mut current_island); if current_island.is_empty() { continue; } let min_col = current_island.iter() .map(|&(_, c)| c).min().unwrap(); let normalized: Vec<(i32, i32)> = current_island .iter() .map(|&(r, c)| (r - row as i32, c - min_col)) .collect(); if !unique_islands.iter().any(|other| *other == normalized) { unique_islands.push(normalized); } } } unique_islands.len() as i32 } }

::tabs-end

复杂度分析

时间复杂度：$O(M^2 \cdot N^2)$
空间复杂度：$O(N \cdot M)$

其中 $M$ 为行数，$N$ 为列数。

暴力方案的瓶颈在于：每发现一个新岛屿，都要与所有已存岛屿做一次 O(面积) 的逐格比较，最坏情况下岛屿数量与网格面积同阶，因此总代价达到平方级。

方案二：局部坐标哈希（Hash By Local Coordinates）

直觉

与其把新岛屿与历史岛屿一一比较，不如把"判断是否重复"交给哈希集合：每个岛屿表示为相对坐标的集合（即相对起点的偏移集合）。在 Python 中，坐标元组的集合可用frozenset冻结，天然可哈希；两个形状相同的岛屿会得到完全相同的相对坐标集合，于是重复形状会被哈希集合自动去重。查找由 O(唯一岛屿数) 降为 O(1)。

算法步骤

用dfs探索每个岛屿，把格子存为相对起点的坐标(row - row_origin, col - col_origin)；
将坐标集合转换为frozenset（或其他语言的等价可哈希结构）；
把frozenset加入唯一岛屿集合；
返回唯一岛屿集合的大小。

多语言实现

::tabs-start

class Solution: def numDistinctIslands(self, grid: List[List[int]]) -> int: # Do a DFS to find all cells in the current island. def dfs(row, col): if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]): return if (row, col) in seen or not grid[row][col]: return seen.add((row, col)) current_island.add((row - row_origin, col - col_origin)) dfs(row + 1, col) dfs(row - 1, col) dfs(row, col + 1) dfs(row, col - 1) # Repeatedly start DFS's as long as there are islands remaining. seen = set() unique_islands = set() for row in range(len(grid)): for col in range(len(grid[0])): current_island = set() row_origin = row col_origin = col dfs(row, col) if current_island: unique_islands.add(frozenset(current_island)) return len(unique_islands)

class Solution { private int[][] grid; private boolean[][] seen; private Set<Pair<Integer, Integer>> currentIsland; private int currRowOrigin; private int currColOrigin; private void dfs(int row, int col) { if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length) { return; } if (grid[row][col] == 0 || seen[row][col]) { return; } seen[row][col] = true; currentIsland.add(new Pair<>(row - currRowOrigin, col - currColOrigin)); dfs(row + 1, col); dfs(row - 1, col); dfs(row, col + 1); dfs(row, col - 1); } public int numDistinctIslands(int[][] grid) { this.grid = grid; this.seen = new boolean[grid.length][grid[0].length]; Set<Set<Pair<Integer, Integer>>> islands = new HashSet<>(); for (int row = 0; row < grid.length; row++) { for (int col = 0; col < grid[0].length; col++) { this.currentIsland = new HashSet<>(); this.currRowOrigin = row; this.currColOrigin = col; dfs(row, col); if (!currentIsland.isEmpty()) { islands.add(currentIsland); } } } return islands.size(); } }

impl Solution { pub fn num_distinct_islands(grid: Vec<Vec<i32>>) -> i32 { let rows = grid.len(); let cols = grid[0].len(); let mut seen = vec![vec![false; cols]; rows]; let mut islands: HashSet<BTreeSet<(i32, i32)>> = HashSet::new(); fn dfs( grid: &[Vec<i32>], seen: &mut Vec<Vec<bool>>, r: i32, c: i32, origin_r: i32, origin_c: i32, island: &mut BTreeSet<(i32, i32)>, ) { if r < 0 || c < 0 || r >= grid.len() as i32 || c >= grid[0].len() as i32 { return; } let (ru, cu) = (r as usize, c as usize); if grid[ru][cu] == 0 || seen[ru][cu] { return; } seen[ru][cu] = true; island.insert((r - origin_r, c - origin_c)); dfs(grid, seen, r + 1, c, origin_r, origin_c, island); dfs(grid, seen, r - 1, c, origin_r, origin_c, island); dfs(grid, seen, r, c + 1, origin_r, origin_c, island); dfs(grid, seen, r, c - 1, origin_r, origin_c, island); } for row in 0..rows { for col in 0..cols { let mut current_island = BTreeSet::new(); dfs(&grid, &mut seen, row as i32, col as i32, row as i32, col as i32, &mut current_island); if !current_island.is_empty() { islands.insert(current_island); } } } islands.len() as i32 } }

::tabs-end

复杂度分析

时间复杂度：$O(M \cdot N)$
空间复杂度：$O(M \cdot N)$

其中 $M$ 为行数，$N$ 为列数。

这里的时间复杂度退化为与网格大小线性相关：每个格子至多被 DFS 访问一次，而哈希集合的插入与判重均为 O(1) 摊还代价。一个值得注意的语言细节是：Rust 实现使用BTreeSet而非HashSet作为岛内坐标容器，因为BTreeSet的元素有确定的全序，能保证"形状相同 ⇔ 集合相等"这一等价关系不因哈希序而失真。

方案三：路径签名哈希（Hash By Path Signature）

直觉

识别岛屿形状还可以不记录坐标，而是记录DFS 的遍历路径。只要每次 DFS 都以固定顺序探索四个方向（如下、上、右、左），两个形状相同的岛屿必然产生完全相同的方向序列。关键细节是：在从当前格子回溯时，也要记录一个回溯标记（如"0"）。缺少回溯标记，不同的形状可能产生相同的方向序列（例如"直条"与"L 形"某些情况下方向串会混淆），导致误判为同一岛屿。

算法步骤

用dfs探索每个岛屿，记录每次移动的方向（D、U、R、L 分别对应下、上、右、左）；
在遍历完某个格子的所有邻居后，追加回溯标记（例如"0"）；
把路径签名转换为字符串，加入唯一岛屿集合；
返回唯一岛屿集合的大小。

多语言实现

::tabs-start

class Solution: def numDistinctIslands(self, grid: List[List[int]]) -> int: # Do a DFS to find all cells in the current island. def dfs(row, col, direction): if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]): return if (row, col) in seen or not grid[row][col]: return seen.add((row, col)) path_signature.append(direction) dfs(row + 1, col, "D") dfs(row - 1, col, "U") dfs(row, col + 1, "R") dfs(row, col - 1, "L") path_signature.append("0") # Repeatedly start DFS's as long as there are islands remaining. seen = set() unique_islands = set() for row in range(len(grid)): for col in range(len(grid[0])): path_signature = [] dfs(row, col, "0") if path_signature: unique_islands.add(tuple(path_signature)) return len(unique_islands)

class Solution { private int[][] grid; private boolean[][] visited; private StringBuffer currentIsland; public int numDistinctIslands(int[][] grid) { this.grid = grid; this.visited = new boolean[grid.length][grid[0].length]; Set<String> islands = new HashSet<>(); for (int row = 0; row < grid.length; row++) { for (int col = 0; col < grid[0].length; col++) { currentIsland = new StringBuffer(); dfs(row, col, '0'); if (currentIsland.length() == 0) { continue; } islands.add(currentIsland.toString()); } } return islands.size(); } private void dfs(int row, int col, char dir) { if (row < 0 || col < 0 || row >= grid.length || col >= grid[0].length) { return; } if (visited[row][col] || grid[row][col] == 0) { return; } visited[row][col] = true; currentIsland.append(dir); dfs(row + 1, col, 'D'); dfs(row - 1, col, 'U'); dfs(row, col + 1, 'R'); dfs(row, col - 1, 'L'); currentIsland.append('0'); } }

class Solution { private: vector<vector<int>>* grid; vector<vector<bool>> visited; string currentIsland; void dfs(int row, int col, char dir) { if (row < 0 || col < 0 || row >= grid->size() || col >= (*grid)[0].size()) { return; } if (visited[row][col] || (*grid)[row][col] == 0) { return; } visited[row][col] = true; currentIsland += dir; dfs(row + 1, col, 'D'); dfs(row - 1, col, 'U'); dfs(row, col + 1, 'R'); dfs(row, col - 1, 'L'); currentIsland += '0'; } public: int numDistinctIslands(vector<vector<int>>& grid) { this->grid = &grid; visited = vector<vector<bool>>(grid.size(), vector<bool>(grid[0].size(), false)); unordered_set<string> islands; for (int row = 0; row < grid.size(); row++) { for (int col = 0; col < grid[0].size(); col++) { currentIsland = ""; dfs(row, col, '0'); if (currentIsland.empty()) { continue; } islands.insert(currentIsland); } } return islands.size(); } };

class Solution { /** * @param {number[][]} grid * @return {number} */ numDistinctIslands(grid) { this.grid = grid; this.visited = Array.from({ length: grid.length }, () => Array(grid[0].length).fill(false), ); const islands = new Set(); for (let row = 0; row < grid.length; row++) { for (let col = 0; col < grid[0].length; col++) { this.currentIsland = []; this.dfs(row, col, '0'); if (this.currentIsland.length === 0) { continue; } islands.add(this.currentIsland.join('')); } } return islands.size; } dfs(row, col, dir) { if ( row < 0 || col < 0 || row >= this.grid.length || col >= this.grid[0].length ) { return; } if (this.visited[row][col] || this.grid[row][col] === 0) { return; } this.visited[row][col] = true; this.currentIsland.push(dir); this.dfs(row + 1, col, 'D'); this.dfs(row - 1, col, 'U'); this.dfs(row, col + 1, 'R'); this.dfs(row, col - 1, 'L'); this.currentIsland.push('0'); } }

public class Solution { private int[][] grid; private bool[,] visited; private StringBuilder currentIsland; public int NumDistinctIslands(int[][] grid) { this.grid = grid; int rows = grid.Length, cols = grid[0].Length; visited = new bool[rows, cols]; HashSet<string> islands = new HashSet<string>(); for (int row = 0; row < rows; row++) { for (int col = 0; col < cols; col++) { currentIsland = new StringBuilder(); Dfs(row, col, '0'); if (currentIsland.Length == 0) continue; islands.Add(currentIsland.ToString()); } } return islands.Count; } private void Dfs(int row, int col, char dir) { if (row < 0 || col < 0 || row >= grid.Length || col >= grid[0].Length) { return; } if (visited[row, col] || grid[row][col] == 0) { return; } visited[row, col] = true; currentIsland.Append(dir); Dfs(row + 1, col, 'D'); Dfs(row - 1, col, 'U'); Dfs(row, col + 1, 'R'); Dfs(row, col - 1, 'L'); currentIsland.Append('0'); } }

func numDistinctIslands(grid [][]int) int { rows, cols := len(grid), len(grid[0]) visited := make([][]bool, rows) for i := range visited { visited[i] = make([]bool, cols) } islands := make(map[string]bool) var currentIsland strings.Builder var dfs func(row, col int, dir byte) dfs = func(row, col int, dir byte) { if row < 0 || col < 0 || row >= rows || col >= cols { return } if visited[row][col] || grid[row][col] == 0 { return } visited[row][col] = true currentIsland.WriteByte(dir) dfs(row+1, col, 'D') dfs(row-1, col, 'U') dfs(row, col+1, 'R') dfs(row, col-1, 'L') currentIsland.WriteByte('0') } for row := 0; row < rows; row++ { for col := 0; col < cols; col++ { currentIsland.Reset() dfs(row, col, '0') if currentIsland.Len() == 0 { continue } islands[currentIsland.String()] = true } } return len(islands) }

class Solution { private lateinit var grid: Array<IntArray> private lateinit var visited: Array<BooleanArray> private lateinit var currentIsland: StringBuilder fun numDistinctIslands(grid: Array<IntArray>): Int { this.grid = grid val rows = grid.size val cols = grid[0].size visited = Array(rows) { BooleanArray(cols) } val islands = HashSet<String>() for (row in 0 until rows) { for (col in 0 until cols) { currentIsland = StringBuilder() dfs(row, col, '0') if (currentIsland.isEmpty()) continue islands.add(currentIsland.toString()) } } return islands.size } private fun dfs(row: Int, col: Int, dir: Char) { if (row < 0 || col < 0 || row >= grid.size || col >= grid[0].size) { return } if (visited[row][col] || grid[row][col] == 0) { return } visited[row][col] = true currentIsland.append(dir) dfs(row + 1, col, 'D') dfs(row - 1, col, 'U') dfs(row, col + 1, 'R') dfs(row, col - 1, 'L') currentIsland.append('0') } }

class Solution { private var grid: [[Int]] = [] private var visited: [[Bool]] = [] private var currentIsland: [Character] = [] func numDistinctIslands(_ grid: [[Int]]) -> Int { self.grid = grid let rows = grid.count, cols = grid[0].count visited = Array(repeating: Array(repeating: false, count: cols), count: rows) var islands = Set<String>() for row in 0..<rows { for col in 0..<cols { currentIsland = [] dfs(row, col, "0") if currentIsland.isEmpty { continue } islands.insert(String(currentIsland)) } } return islands.count } private func dfs(_ row: Int, _ col: Int, _ dir: Character) { if row < 0 || col < 0 || row >= grid.count || col >= grid[0].count { return } if visited[row][col] || grid[row][col] == 0 { return } visited[row][col] = true currentIsland.append(dir) dfs(row + 1, col, "D") dfs(row - 1, col, "U") dfs(row, col + 1, "R") dfs(row, col - 1, "L") currentIsland.append("0") } }

impl Solution { pub fn num_distinct_islands(grid: Vec<Vec<i32>>) -> i32 { let rows = grid.len(); let cols = grid[0].len(); let mut visited = vec![vec![false; cols]; rows]; let mut islands: HashSet<String> = HashSet::new(); fn dfs( grid: &[Vec<i32>], visited: &mut Vec<Vec<bool>>, row: i32, col: i32, dir: u8, path: &mut Vec<u8>, ) { if row < 0 || col < 0 || row >= grid.len() as i32 || col >= grid[0].len() as i32 { return; } let (r, c) = (row as usize, col as usize); if visited[r][c] || grid[r][c] == 0 { return; } visited[r][c] = true; path.push(dir); dfs(grid, visited, row + 1, col, b'D', path); dfs(grid, visited, row - 1, col, b'U', path); dfs(grid, visited, row, col + 1, b'R', path); dfs(grid, visited, row, col - 1, b'L', path); path.push(b'0'); } for row in 0..rows { for col in 0..cols { let mut path = Vec::new(); dfs(&grid, &mut visited, row as i32, col as i32, b'0', &mut path); if !path.is_empty() { islands.insert( String::from_utf8(path).unwrap(), ); } } } islands.len() as i32 } }

::tabs-end

复杂度分析

时间复杂度：$O(M \cdot N)$
空间复杂度：$O(M \cdot N)$

其中 $M$ 为行数，$N$ 为列数。

路径签名方案的额外优点是实现极其简洁：不需要维护坐标列表，只需要一个累积字符串/字符数组，且签名天然是字符串，任何语言都可以直接作为哈希键。这也是该方案在工程与面试中最常被采用的原因。

三种方案对比

方案	签名形式	判重方式	时间复杂度	空间复杂度	代码复杂度
暴力比较	归一化后的坐标列表	与已存岛屿逐格比较	$O(M^2 \cdot N^2)$	$O(N \cdot M)$	较高（需要独立判重函数）
局部坐标哈希	相对坐标的（冻结）集合	哈希集合 O(1) 判重	$O(M \cdot N)$	$O(M \cdot N)$	中等
路径签名哈希	DFS 方向串 + 回溯标记	哈希集合 O(1) 判重	$O(M \cdot N)$	$O(M \cdot N)$	最低

三者在"DFS 遍历网格"这一层完全一致——都遵循 python/0200-number-of-islands.py 中展示的经典模式：seen集合防止重复访问、四方向递归、主循环逐个格子发起 DFS；差异只在于拿到岛屿后如何构造签名。这也是 LeetCode 岛屿系列题（如最大岛屿面积、封闭岛屿、岛屿数量 II、岛屿与宝藏）可以复用同一套遍历框架、只改"收尾逻辑"的原因。

常见陷阱（Common Pitfalls）

陷阱一：忘记归一化岛屿坐标

比较岛屿时，必须把每个格子相对一个一致的原点（通常是第一个发现的格子）平移记录。不做归一化的话，网格中不同位置的两个相同形状会被误判为不同岛屿，导致唯一岛屿数量被高估。方案一、二的核心都是归一化，方案三则通过固定遍历顺序与方向编码隐式完成了归一化。

陷阱二：路径签名中缺失回溯标记

采用路径哈希时，仅记录每次 DFS 移动的方向是不够的。不同的岛屿形状可能产生相同的方向序列——若不在从递归调用返回时追加标记（如"0"），就无法区分"分支结构"与"直行结构"。务必在遍历完一个格子的全部邻居后追加回溯标记，让签名能够精确还原树形遍历结构。

陷阱三：用可变数据结构作为哈希键

在 Python 中，直接用list或set作为字典键/集合元素会报TypeError: unhashable type，必须先转换为不可变类型（如frozenset、tuple）再存入唯一岛屿集合。同理，Java 中若使用自定义对象表示岛屿，必须正确实现hashCode()与equals()，否则哈希判重会失效或产生错误结果。