📃 题目描述

题目链接：

• 200. 岛屿数量 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

类似题目：剑指 Offer II 116. 省份数量 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

🔔 解题思路

和上道题 剑指 Offer II 105. 岛屿的最大面积 - 力扣（LeetCode） (leetcode-cn.com) (opens new window) 思路一样，这里就当自测下吧

DFS

连通性问题用 DFS 做效率更高

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid[0].length == 0) {
            return 0;
        }

        // 岛屿的数量
        int num = 0;

        boolean[][] visited = new boolean[grid.length][grid[0].length];

        for (int i = 0; i < grid.length; i ++) {
            for (int j = 0; j < grid[0].length; j ++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    // dfs grid[row][col] 所在的岛屿，更新 visited
                    dfs(grid, visited, i, j);
                    // 岛屿数量 + 1
                    num ++;
                }
            }
        }

        return num;
    }
	
    // dfs grid[row][col] 所在的岛屿，更新 visited
    private void dfs(char[][] grid, boolean[][] visited, int row, int col) {
        visited[row][col] = true;
		
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
		
        // dfs grid[row][col] 的相邻陆地节点
        for (int[] dir : dirs) {
            int i = row + dir[0];
            int j = col + dir[1];

            if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && 
            !visited[i][j] && grid[i][j] == '1') {
                dfs(grid, visited, i, j);
            }
        }
    }
}

BFS

class Solution {
    public int numIslands(char[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;

        // 标识每个格子是否被访问过
        boolean[][] visited = new boolean[rows][cols];

        // 岛屿的数量
        int count = 0;

        for (int i = 0; i < rows; i ++) {
            for (int j = 0; j < cols; j ++) {
                // 如果遇到一个值为 1 的格子并且它不在之前已知的岛屿上，那么就到达了一个新的岛屿
                if (grid[i][j] == '1' && !visited[i][j]) {
                    count ++;
                    // 搜索这个新岛屿
                    bfs(grid, visited, i, j);
                }
            }
        }

        return count;
    }

    // BFS grid[row, col] 所在岛屿
    private void bfs(char[][] grid, boolean[][] visited, int row, int col) {
        // 队列中用数组存储每个格子的坐标
        Queue<int[]> queue = new LinkedList<>();
        // 起始节点入队
        queue.offer(new int[]{row, col});
        // 记录当前节点是否访问过
        visited[row][col] = true;

        // 上下左右四个方向
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int k = 0; k < size; k ++) {
                // 从队列中取出一个节点
                int[] pos = queue.poll();
                
                // 上下左右四个方向上值为 1 的格子依次入队
                for (int[] dir : dirs) {
                    int i = pos[0] + dir[0]; // 横坐标
                    int j = pos[1] + dir[1]; // 纵坐标

                    if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && 
                        grid[i][j] == '1' && !visited[i][j]) {
                        queue.offer(new int[]{i, j});
                        visited[i][j] = true;
                    }
                }
            }
        }

    }
}

对于层序遍历来说，如果我们不需要存储每一层遍历的结果的话，其实那个 for (int k = 0; k < size; k ++) 循环是可以省略掉的，如下：

// BFS grid[row, col] 所在岛屿
private void bfs(char[][] grid, boolean[][] visited, int row, int col) {
    // 队列中用数组存储每个格子的坐标
    Queue<int[]> queue = new LinkedList<>();
    // 起始节点入队
    queue.offer(new int[]{row, col});
    // 记录当前节点是否访问过
    visited[row][col] = true;

    // 上下左右四个方向
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    while (!queue.isEmpty()) {
        int size = queue.size();
        // 从队列中取出一个节点
        int[] pos = queue.poll();

        // 上下左右四个方向上值为 1 的格子依次入队
        for (int[] dir : dirs) {
            int i = pos[0] + dir[0]; // 横坐标
            int j = pos[1] + dir[1]; // 纵坐标

            if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && 
                grid[i][j] == '1' && !visited[i][j]) {
                queue.offer(new int[]{i, j});
                visited[i][j] = true;
            }
        }
    }

}
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：