转载

LeetCode 200：岛屿数量 Number of Islands

题目：

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

Given a 2d grid map of’1’s (land) and’0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

示例 1:

示例 2:

解题思路：

首先明白岛屿的定义：一块 1 周围全是 0，即为一个岛屿。（注意：grid 数组内的 1、0 均为char型字符，非整型）

示例1 中所有 1 都可以连接到一起，即所有 1 组成一个岛屿。示例2 中的三个岛屿：左上角四个1、中间一个1、右下角一个一，分别组成三个岛屿。

Flood fill算法是从一个区域中提取若干个连通的点与其他相邻区域区分开（或分别染成不同颜色）的经典算法。因为其思路类似洪水从一个区域扩散到所有能到达的区域而得名。在 GNU Go 和扫雷中，Flood Fill算法被用来计算需要被清除的区域。由上述定义可看出该题是典型的 Flood fill 算法类型例题，将岛屿与水分开，并染成特定颜色，以记录已累加过该岛屿。

每块岛屿可以看成相连的一个个节点，只需把所有相连节点遍历殆尽并标上特殊值以记录该节点已访问过，则遍历殆尽时证明一块岛屿已找到。

三种解题方法：

DFS（深度优先搜索）：从一个为1的根节点开始访问，从每个相邻1节点向下访问到顶点（周围全是水），依次访问其他相邻1节点到顶点
BFS（广度优先搜索）：从一个为1的根节点开始访问，每次向下访问一个节点，直到访问到最后一个顶点
并查集：也被称为联合查找数据结构，因为它主要由联合、查找两个过程实现：
Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union：将两个子集合并成同一个集合。

针对该题即先以一个根节点1作为初始节点，判断周围节点是否为1，如果是则新建一个集合并把该节点作为父节点。之后遍历下一个节点，如果是1则查找该节点的父节点（即第一个节点），并把该节点周围为1的节点的父节点全部指向该节点的父节点，以此类推，直到把该块岛屿所有1 节点加入同一个集合。最后集合个数（父节点的个数）即为岛屿数量

DFS:

时间复杂度 : O(M×N)，其中 M 和 N 分别为行数和列数。

空间复杂度 : 最坏情况下为 O(M×N)，此时整个网格均为陆地，深度优先搜索的深度达到 M×N。

Java：

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int row = grid.length, columns = grid[0].length, count = 0;
        for (int i = 0; i < row; i++) {//遍历所有点
            for (int j = 0; j < columns; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j, row, columns);//dfs遍历所有连接的点
                    count++;//记录岛屿数量
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int i, int j, int row, int columns) {
        if (i < 0 || j < 0 || i >= row || j >= columns || grid[i][j] == '0') return;//基线条件
        grid[i][j] = '0';//遍历过的点置 0
        dfs(grid, i + 1, j, row, columns);
        dfs(grid, i, j + 1, row, columns);
        dfs(grid, i - 1, j, row, columns);
        dfs(grid, i, j - 1, row, columns);
    }
}

Python：

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or len(grid) == 'o': return 0
        row, columns = len(grid), len(grid[0])
        count = 0
        for i in range(row):
            for j in range(columns):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j, row, columns)
                    count += 1
        return count

    def dfs(self, grid: List[List[str]], i: int, j: int, row: int, columns: int):
        if i >= row or i < 0 or j >= columns or j < 0 or grid[i][j] == '0': return
        grid[i][j] = '0'
        self.dfs(grid, i - 1, j, row, columns)
        self.dfs(grid, i, j - 1, row, columns)
        self.dfs(grid, i + 1, j, row, columns)
        self.dfs(grid, i, j + 1, row, columns)

BFS：

时间复杂度 : O(M×N)，其中 M 和 N 分别为行数和列数。

空间复杂度 : O( min(M,N) )，在最坏的情况下（全部为陆地），队列的大小可以达到 min(M，N)。

Java：

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int row = grid.length, columns = grid[0].length, count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < columns; j++) {//遍历所有节点
                if (grid[i][j] == '1') {
                    bfs(grid, i, j, row, columns);
                    count++;//记录岛屿数量
                }
            }
        }
        return count;
    }

    private void bfs(char[][] grid, int i, int j, int row, int columns) {
        Queue<Integer> loc = new LinkedList<>();//队列暂存值为 1 的点
        loc.add(i * columns + j);//暂存该点位置，也可以用一个[i,j]数组表示，不过占用空间也会大一倍
        while (!loc.isEmpty()) {
            int id = loc.remove();//取出位置
            int r = id / columns, c = id % columns;//分解位置得到索引
            if (r - 1 >= 0 && grid[r - 1] == '1') {
                loc.add((r - 1) * columns + c);
                grid[r - 1] = '0';
            }
            if (r + 1 < row && grid[r + 1] == '1') {
                loc.add((r + 1) * columns + c);
                grid[r + 1] = '0';
            }
            if (c - 1 >= 0 && grid[r] == '1') {
                loc.add(r * columns + c - 1);
                grid[r] = '0';
            }
            if (c + 1 < columns && grid[r] == '1') {
                loc.add(r * columns + c + 1);
                grid[r] = '0';
            }
        }
    }
}

Python3：

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or len(grid) == 'o': return 0
        row, columns = len(grid), len(grid[0])
        count = 0
        for i in range(row):
            for j in range(columns):
                if grid[i][j] == '1':
                    self.bfs(grid, i, j, row, columns)
                    count += 1
        return count

    def bfs(self, grid: List[List[str]], i: int, j: int, row: int, columns: int):
        queue = collections.deque()
        queue.append((i, j))  # 位置以元组存入队列
        while queue:
            r, c = queue.popleft()
            if r + 1 < row and grid[r + 1] == '1':
                queue.append((r + 1, c))
                grid[r + 1] = '0'
            if r - 1 >= 0 and grid[r - 1] == '1':
                queue.append((r - 1, c))
                grid[r - 1] = '0'
            if c + 1 < columns and grid[r] == '1':
                queue.append((r, c + 1))
                grid[r] = '0'
            if c - 1 >= 0 and grid[r] == '1':
                queue.append((r, c - 1))
                grid[r] = '0'

并查集：

并查集这种解法冗杂且鸡肋，效率很低，以下java代码参考自LeetCode。简单了解其思想扩展一下思路即可：

Java：

class Solution {
    class UnionFind {
        int count; //计数
        int[] parent;
        int[] rank;

        public UnionFind(char[][] grid) {
            count = 0;
            int m = grid.length, n = grid[0].length;
            parent = new int[m * n];
            rank = new int[m * n];
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == '1') {
                        parent[i * n + j] = i * n + j;
                        ++count;
                    }
                    rank[i * n + j] = 0;
                }
            }
        }
        public int find(int i) {
            if (parent[i] != i) parent[i] = find(parent[i]);
            return parent[i];
        }
        public void union(int x, int y) {
            int rootx = find(x);
            int rooty = find(y);
            if (rootx != rooty) {
                if (rank[rootx] > rank[rooty]) {
                    parent[rooty] = rootx;
                } else if (rank[rootx] < rank[rooty]) {
                    parent[rootx] = rooty;
                } else {
                    parent[rooty] = rootx;
                    rank[rootx] += 1;
                }
                --count;
            }
        }
        public int getCount() {
            return count;
        }
    }
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int row = grid.length, columns = grid[0].length;
        UnionFind uf = new UnionFind(grid);
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < columns; ++j) {
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    if (i - 1 >= 0 && grid[i - 1][j] == '1') uf.union(i * columns + j, (i - 1) * columns + j);
                    if (i + 1 < row && grid[i + 1][j] == '1') uf.union(i * columns + j, (i + 1) * columns + j);
                    if (j - 1 >= 0 && grid[i][j - 1] == '1') uf.union(i * columns + j, i * columns + j - 1);
                    if (j + 1 < columns && grid[i][j + 1] == '1') uf.union(i * columns + j, i * columns + j + 1);
                }
            }
        }
        return uf.getCount();
    }
}

LeetCode 200：岛屿数量 Number of Islands