不同岛屿的数量

Submission

运行时间: 55 ms

内存: 16.3 MB

class Solution:
    def numDistinctIslands(self, g) -> int:
        m, n = len(g), len(g[0])
        islands = []
        for i in range(m):
            for j in range(n):
                if g[i][j] == 1:
                    tmp, g[i][j], k = [0, 0], 0, 0
                    while k < len(tmp):
                        r, c = tmp[k] + i, tmp[k+1] + j
                        if r > 0 and g[r-1][c] == 1:
                            g[r-1][c] = 0
                            tmp.append(r-1-i)
                            tmp.append(c-j)
                        if r < m - 1 and g[r+1][c] == 1:
                            g[r+1][c] = 0
                            tmp.append(r+1-i)
                            tmp.append(c-j)
                        if c > 0 and g[r][c-1] == 1:
                            g[r][c-1] = 0
                            tmp.append(r-i)
                            tmp.append(c-j-1)
                        if c < n-1 and g[r][c+1] == 1:
                            g[r][c+1] = 0
                            tmp.append(r-i)
                            tmp.append(c+1-j)
                        k += 2
                    islands.append(tmp)
        if not islands:
            return 0
        islands.sort()
        res = 0
        for i in range(1, len(islands)):
            if islands[i] != islands[i-1]:
                res += 1
        return res + 1

Explain

该题目的目标是找出二维网格中不同的岛屿数量，其中岛屿由相邻（上下左右）的1组成。解题思路是通过深度优先搜索（DFS）遍历每个岛屿，同时将遍历过的岛屿上的1修改为0，以防止重复计数。对于每个岛屿，记录其形状的相对坐标。将每个岛屿的形状存入列表中，最后对列表中的形状进行排序，并通过比较相邻形状来统计不同岛屿的数量。

时间复杂度: O(MN)

空间复杂度: O(MN)

class Solution:
    def numDistinctIslands(self, g) -> int:
        m, n = len(g), len(g[0])
        islands = []
        for i in range(m):
            for j in range(n):
                if g[i][j] == 1:
                    tmp, g[i][j], k = [0, 0], 0, 0
                    while k < len(tmp):
                        r, c = tmp[k] + i, tmp[k+1] + j
                        if r > 0 and g[r-1][c] == 1:
                            g[r-1][c] = 0
                            tmp.append(r-1-i)
                            tmp.append(c-j)
                        if r < m - 1 and g[r+1][c] == 1:
                            g[r+1][c] = 0
                            tmp.append(r+1-i)
                            tmp.append(c-j)
                        if c > 0 and g[r][c-1] == 1:
                            g[r][c-1] = 0
                            tmp.append(r-i)
                            tmp.append(c-1-j)
                        if c < n-1 and g[r][c+1] == 1:
                            g[r][c+1] = 0
                            tmp.append(r-i)
                            tmp.append(c+1-j)
                        k += 2
                    islands.append(tmp)
        if not islands:
            return 0
        islands.sort()
        res = 0
        for i in range(1, len(islands)):
            if islands[i] != islands[i-1]:
                res += 1
        return res + 1

Explore

使用相对坐标而不是绝对坐标可以确保岛屿的比较是基于其结构而不是位置。这意味着即使两个岛屿在网格中的不同位置，只要它们的形状和结构相同，它们就被认为是相同的岛屿。这种方法使得岛屿的比较独立于它们在网格中的具体位置，能够更准确地统计不同岛屿的数量。

确实，`tmp`列表在遍历大型岛屿时可能会增长得非常大，这会消耗大量内存并可能影响性能。为了优化，可以考虑使用哈希表来存储访问过的坐标，这样可以在不重复存储相同坐标的情况下，有效地检查和标记已访问的位置。此外，可以探索使用更紧凑的数据结构来存储坐标信息，如使用二元组代替单独的列表元素。

依赖于`tmp`列表长度的动态变化确实可能导致逻辑复杂和效率低下，因为它要求在循环内部修改列表同时又遍历该列表。使用队列可以优化这一过程。通过队列，可以实现先进先出的顺序，每次从队列的前端取出当前节点进行处理，并将新发现的节点加入队列的后端。这样可以使代码逻辑更清晰，且在性能上更为稳定。

列边界的检查是非常重要的，如果没有进行适当的边界检查，代码可能会尝试访问数组外的元素，从而导致运行时错误。在代码中应该添加对`c-1`和`c+1`的检查，确保这些值在有效范围内，从而避免越界错误。这不仅能保证程序的稳定性，还能防止潜在的安全风险。