200. 岛屿数量

这个问题是典型的图遍历问题，可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来解决。基本思路是遍历网格，每当发现一块未访问的陆地('1')，就说明找到了一个新的岛屿，然后通过DFS或BFS将这个岛屿上所有相连的陆地标记为已访问。

深度优先搜索(DFS)解法

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

        int rows = grid.length;
        int cols = grid[0].length;
        int count = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }

        return count;
    }

    private void dfs(char[][] grid, int row, int col) {
        int rows = grid.length;
        int cols = grid[0].length;

        // 边界检查
        if (row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] == '0') {
            return;
        }

        // 将当前陆地标记为已访问（改为水）
        grid[row][col] = '0';

        // 递归访问四个方向
        dfs(grid, row - 1, col); // 上
        dfs(grid, row + 1, col); // 下
        dfs(grid, row, col - 1); // 左
        dfs(grid, row, col + 1); // 右
    }
}

广度优先搜索(BFS)解法

import java.util.LinkedList;
import java.util.Queue;

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

        int rows = grid.length;
        int cols = grid[0].length;
        int count = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    bfs(grid, i, j);
                }
            }
        }

        return count;
    }

    private void bfs(char[][] grid, int startRow, int startCol) {
        int rows = grid.length;
        int cols = grid[0].length;

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{startRow, startCol});
        grid[startRow][startCol] = '0'; // 标记为已访问

        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int row = cell[0];
            int col = cell[1];

            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];

                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] == '1') {
                    queue.offer(new int[]{newRow, newCol});
                    grid[newRow][newCol] = '0'; // 标记为已访问
                }
            }
        }
    }
}

复杂度分析

• 时间复杂度：O(M×N)，其中M是网格的行数，N是网格的列数。需要遍历整个网格一次。
• 空间复杂度：
  • DFS：最坏情况下O(M×N)，当整个网格都是陆地时，递归调用栈的深度可能达到M×N。
  • BFS：最坏情况下O(min(M,N))，队列的最大大小取决于网格的较小维度。

两种方法都能有效解决问题，DFS通常代码更简洁，而BFS在网格较大时可以避免栈溢出的风险。