LeetCode.200.Number of Islands 岛屿个数

题目描述

200 Number of Islands
https://leetcode-cn.com/problems/number-of-islands/

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.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

---

相似题目

LeetCode.695.Max Area of Island 岛屿的最大面积
LeetCode.200.Number of Islands 岛屿个数

---

解题过程

DFS深度优先搜索-递归

时间复杂度 O(mn) 空间复杂度 O(mn)

private static class SolutionV2020Recursive {
    int numRows, numColumns;
    int[] dx = {-1, 0, 1,  0};
    int[] dy = { 0, 1, 0, -1};
    public int numIslands(char[][] grid) {
        if (null == grid || 0 == grid.length) {
            return 0;
        }
        numRows = grid.length;
        numColumns = grid[0].length;

        int islandsCount = 0;
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numColumns; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    islandsCount++;
                }
            }
        }
        return islandsCount;
    }

    // 从 (x,y) 开始一次深度优先搜索，把访问过的'1'都置为'0'
    private void dfs(char[][] grid, int x, int y) {
        if (x < 0 || y < 0 || x >= numRows || y >= numColumns || grid[x][y] != '1') {
            return;
        }
        grid[x][y] = '0';
        for (int k = 0; k < 4; k++) {
            dfs(grid, x + dx[k], y + dy[k]);
        }
    }
}

DFS深度优先搜索-迭代

遍历二位数组，遇到 ‘1’ 就开始一次 深度优先搜索DFS ，每次dfs可遍历一座岛，dfs过程中将遍历过的结点设为’0’，dfs的次数就是岛的个数。
我写的是用 栈 的非递归写法，用递归写会更简单。

时间复杂度 O(mn) 空间复杂度 O(mn)

private static class SolutionV2020Iterative {
    public int numIslands(char[][] grid) {
        if (null == grid || grid.length == 0) {
            return 0;
        }
        int islandsCount = 0;
        int rows = grid.length, columns = grid[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (grid[i][j] == '1') {
                    // 开始一次dfs， 每次dfs可遍历一座岛，dfs的次数就是岛的个数
                    dfs(grid, i, j);
                    islandsCount++;
                }
            }
        }
        return islandsCount;
    }

    // 从位置[row][column]开始深度优先搜索访问二维数组grid，将访问过的1设为0
    private void dfs(char[][] grid, int row, int column) {
        Deque<Pair<Integer, Integer>> stack = new LinkedList<>();
        grid[row][column] = '0';
        stack.push(new Pair(row, column));
        while (!stack.isEmpty()) {
            Pair<Integer, Integer> pair = stack.element();
            int i = pair.getKey(), j = pair.getValue();
            if (i - 1 >= 0 && grid[i-1][j] == '1') { // 往上
                grid[i-1][j] = '0';
                stack.push(new Pair(i-1, j));
            } else if (j - 1 >= 0 && grid[i][j-1] == '1') { // 往左
                grid[i][j-1] = '0';
                stack.push(new Pair(i, j-1));
            } else if (i + 1 < grid.length && grid[i + 1][j] == '1') { // 往下
                grid[i + 1][j] = '0';
                stack.push(new Pair(i + 1, j));
            } else if (j + 1 < grid[0].length && grid[i][j+1] == '1') { // 往右
                grid[i][j+1] = '0';
                stack.push(new Pair(i, j+1));
            } else {
                stack.pop();
            }
        }
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_200_NumberOfIslands.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_200_NumberOfIslands.java

---