Jianbo Dai's

mq008.岛屿数量

 
  • Dec 03, 2020

题目链接

啊这个题之前有看见过不过那个时候还是很早的时候没什么思路，然后就看了一眼别人的思路，原来就是一个状态空间搜索而已，就用递归写出来了，虽然感觉好像写得没有别人的简洁（见实现2）。这个算法的时间复杂度是O（N），空间复杂度是O（1）（我也不知道多少，如果考虑是在原先的grid上更改的话应该是O（1））。

class Solution:
    def numIslands1(self, grid: List[List[str]]) -> int:
        self.dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        self.grid = grid
        cnt = 0
        self.lrow, self.lcol = len(grid), len(grid[0])
        for i in range(self.lrow):
            for j in range(self.lcol):
                pos = (i, j)
                if self.judgeIsland(pos):
                    cnt += 1
                    self.clearIsland(pos)
        return cnt
    
    def clearIsland(self, pos):
        self.grid[pos[0]][pos[1]] = "0"
        for d in self.dirs:
            neigbour = (pos[0]+d[0], pos[1]+d[1])
            if 0 <= neigbour[0] < self.lrow and 0 <= neigbour[1] < self.lcol:
                if self.judgeIsland(neigbour):
                    self.clearIsland(neigbour)

    def judgeIsland(self, pos):
        return self.grid[pos[0]][pos[1]] == "1"

    def numIslands2(self, grid: [[str]]) -> int:
        def dfs(grid, i, j):
            if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] == '0': return
            grid[i][j] = '0'
            dfs(grid, i + 1, j)
            dfs(grid, i, j + 1)
            dfs(grid, i - 1, j)
            dfs(grid, i, j - 1)
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    dfs(grid, i, j)
                    count += 1
        return count
Search