213 - 200 岛屿数量

题目

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入: 11110 11010 11000 00000

输出: 1

示例 2:

输入: 11000 11000 00100 00011

输出: 3

解答

https://leetcode-cn.com/problems/number-of-islands/solution/dfs-bfs-bing-cha-ji-python-dai-ma-java-dai-ma-by-l/

flood fill：从一个点开始，深度优先/广度优先遍历，找到所有的的连通区域

深度优先

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
        m = len(grid)
        if m == 0:
            return 0
        n = len(grid[0])
        marked = [[False for _ in range(n)] for _ in range(m)]
        count = 0

        def dfs(i, j):
            marked[i][j] = True
            for direction in directions:
                new_i = i + direction[0]
                new_j = j + direction[1]
                if 0 <= new_i and new_i < m and 0 <= new_j and new_j < n and \
                        not marked[new_i][new_j] and grid[new_i][new_j] == "1":
                    dfs(new_i, new_j)

        for i in range(m):
            for j in range(n):
                if not marked[i][j] and grid[i][j] == "1":
                    count += 1
                    dfs(i, j)
        return count

Runtime: 180 ms, faster than 17.23% of Python3 online submissions for Number of Islands.

Memory Usage: 13.8 MB, less than 67.52% of Python3 online submissions for Number of Islands.

python里面，光[0]*3，这是浅拷贝，需要[0 for _ in range(n)]才行。。

广度优先

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        from collections import deque
        m = len(grid)
        if m == 0:
            return 0
        n = len(grid[0])
        marked = [[False for _ in range(n)] for _ in range(m)]
        count = 0

        def bfs(i, j):
            queue = deque()
            queue.append((i, j))
            marked[i][j] = True
            while queue:
                cur_x, cur_y = queue.popleft()
                directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
                for direction in directions:
                    new_i = cur_x + direction[0]
                    new_j = cur_y + direction[1]
                    if 0 <= new_i and new_i < m and 0 <= new_j and \
                            new_j < n and not marked[new_i][new_j] and\
                            grid[new_i][new_j] == "1":
                        queue.append((new_i, new_j))
                        marked[new_i][new_j] = True

        for i in range(m):
            for j in range(n):
                if not marked[i][j] and grid[i][j] == "1":
                    count += 1
                    bfs(i, j)

        return count

Runtime: 196 ms, faster than 11.96% of Python3 online submissions for Number of Islands.

Memory Usage: 13.6 MB, less than 98.29% of Python3 online submissions for Number of Islands.

dfs之挖人工湖

https://leetcode.com/problems/number-of-islands/discuss/56359/Very-concise-Java-AC-solution

就是把遇到的岛屿全部填成水，就可以少一个markded列表来记录了

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        if m == 0:
            return 0
        n = len(grid[0])
        count = 0

        def dfs(i, j):
            if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] == "0":
                return
            grid[i][j] = "0"
            dfs(i+1, j)
            dfs(i, j+1)
            dfs(i-1, j)
            dfs(i, j-1)

        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    count += 1
                    dfs(i, j)

        return count

Runtime: 152 ms, faster than 47.88% of Python3 online submissions for Number of Islands.

Memory Usage: 13.7 MB, less than 82.05% of Python3 online submissions for Number of Islands.

光头大佬的版本

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def sink(i, j):
            if 0 <= i and i < len(grid) and 0 <= j and j < len(grid[i]) and\
                    grid[i][j] == "1":
                grid[i][j] = "0"
                list(map(sink, (i+1, i-1, i, i), (j, j, j+1, j-1)))
                return 1
            return 0
        return sum(sink(i, j) for i in range(len(grid)) for j in range(len(grid[i])))

Runtime: 416 ms, faster than 5.14% of Python3 online submissions for Number of Islands.

Memory Usage: 14.1 MB, less than 26.50% of Python3 online submissions for Number of Islands.

他也是淹岛

image-20200126145519464

笑死我了哈哈哈哈哈