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-startclass 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 DFSs 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 ListListint[] uniqueIslands new ArrayList(); // All known unique islands. private Listint[] 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 (Listint[] otherIsland : uniqueIslands) { if (currentIsland.size() ! otherIsland.size()) { continue; } if (equalIslands(currentIsland, otherIsland)) { return false; } } return true; } private boolean equalIslands(Listint[] island1, Listint[] 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: VecVeci32) - i32 { let rows grid.len(); let cols grid[0].len(); let mut seen vec![vec![false; cols]; rows]; let mut unique_islands: VecVec(i32, i32) Vec::new(); fn dfs( grid: [Veci32], seen: mut VecVecbool, 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-startclass 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 DFSs 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 SetPairInteger, 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]; SetSetPairInteger, 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: VecVeci32) - i32 { let rows grid.len(); let cols grid[0].len(); let mut seen vec![vec![false; cols]; rows]; let mut islands: HashSetBTreeSet(i32, i32) HashSet::new(); fn dfs( grid: [Veci32], seen: mut VecVecbool, 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-startclass 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 DFSs 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]; SetString 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: vectorvectorint* grid; vectorvectorbool 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(vectorvectorint grid) { this-grid grid; visited vectorvectorbool(grid.size(), vectorbool(grid[0].size(), false)); unordered_setstring 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]; HashSetstring islands new HashSetstring(); 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(row1, col, D) dfs(row-1, col, U) dfs(row, col1, 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: ArrayIntArray private lateinit var visited: ArrayBooleanArray private lateinit var currentIsland: StringBuilder fun numDistinctIslands(grid: ArrayIntArray): Int { this.grid grid val rows grid.size val cols grid[0].size visited Array(rows) { BooleanArray(cols) } val islands HashSetString() 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 SetString() 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: VecVeci32) - i32 { let rows grid.len(); let cols grid[0].len(); let mut visited vec![vec![false; cols]; rows]; let mut islands: HashSetString HashSet::new(); fn dfs( grid: [Veci32], visited: mut VecVecbool, row: i32, col: i32, dir: u8, path: mut Vecu8, ) { 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, bD, path); dfs(grid, visited, row - 1, col, bU, path); dfs(grid, visited, row, col 1, bR, path); dfs(grid, visited, row, col - 1, bL, path); path.push(b0); } 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, b0, 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()否则哈希判重会失效或产生错误结果。延伸阅读本题目解文档articles/number-of-distinct-islands.md同框架基础题岛屿数量、python/0200-number-of-islands.py形状/面积相关变体最大岛屿面积、统计子岛屿、封闭岛屿、岛屿数量 II、岛屿与宝藏、岛屿周长【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考