【经典算法】LeetCode 200. 岛屿数量(Java/C/Python3/Go实现含注释说明,中等)

题目描述
思路及实现
- 方式一：深度优先搜索（DFS）
- - 思路
  - 代码实现
  - - Java版本
    - C语言版本
    - Python3版本
    - Golang版本
  - 复杂度分析
- 方式二：使用广度优先搜索（BFS）
- - 思路
  - 代码实现
  - - Java实现
    - C++实现
    - Python3实现
    - Go实现
总结
相似题目

标签(题目类型)：深度优先搜索（DFS）、广度优先搜索（BFS）、并查集（Union Find）

题目描述

给定一个二维字符网格 map，'1' 表示陆地，'0' 表示水域。网格中的每个'1'都被视为一个岛屿的一部分，被水域包围的'1'（水平或垂直四个方向）形成岛屿。找出网格中岛屿的数量。

原题：LeetCode 200. 岛屿数量

思路及实现

方式一：深度优先搜索（DFS）

思路

使用深度优先搜索（DFS）遍历每个单元格，若遇到陆地’1’，则以该点作为起始点开始DFS，将与其相连的所有陆地都标记为已访问（例如，更改为’0’）。每次DFS表示遍历了一个完整的岛屿，岛屿数量加一。

代码实现

Java版本

public class Solution {
    private void dfs(char[][] grid, int i, int j) {
        int m = grid.length;
        int n = grid[0].length;
        
        // 判断边界条件和是否为陆地
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') {
            return;
        }
        
        // 标记为已访问（水域）
        grid[i][j] = '0';
        
        // 递归访问上下左右四个方向的相邻陆地
        dfs(grid, i - 1, j); // 上
        dfs(grid, i + 1, j); // 下
        dfs(grid, i, j - 1); // 左
        dfs(grid, i, j + 1); // 右
    }

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

        int m = grid.length;
        int n = grid[0].length;
        int count = 0;

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

        return count;
    }
}

说明：Java版本使用递归的方式实现了DFS，并通过将已访问的陆地标记为’0’来避免重复计数。

C语言版本

#include <stdbool.h>

void dfs(char** grid, int gridSize, int* gridColSize, int i, int j) {
    if (i < 0 || i >= gridSize || j < 0 || j >= gridColSize[0] || grid[i][j] == '0') {
        return;
    }
    
    grid[i][j] = '0'; // 标记为已访问
    
    dfs(grid, gridSize, gridColSize, i - 1, j); // 上
    dfs(grid, gridSize, gridColSize, i + 1, j); // 下
    dfs(grid, gridSize, gridColSize, i, j - 1); // 左
    dfs(grid, gridSize, gridColSize, i, j + 1); // 右
}

int numIslands(char** grid, int gridSize, int* gridColSize){
    if (grid == NULL || gridSize == 0 || gridColSize[0] == 0) {
        return 0;
    }

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

    return count;
}

说明：C语言版本同样使用DFS，但需要注意二维数组的传递和边界条件的判断。

Python3版本

class Solution:
    def dfs(self, grid, i, j):
        if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] != '1':
            return
        
        grid[i][j] = '0'  # 标记为已访问
        
        # 递归访问上下左右四个方向的相邻陆地
        self.dfs(grid, i - 1, j)  # 上
        self.dfs(grid, i + 1, j)  # 下
        self.dfs(grid, i, j - 1)  # 左
        self.dfs(grid, i, j + 1)  # 右
    
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        count = 0
        
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1':
                    count += 1
                    self.dfs(grid, i, j)
        
        return count

说明：Python3版本同样使用了DFS，但将DFS定义为了类方法，并处理了二维列表的边界条件和访问标记。

Golang版本

func dfs(grid [][]byte, i, j int) {
    rows, cols := len(grid), len(grid[0])
    if i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] != '1' {
        return
    }
    
    grid[i][j] = '0' // 标记为已访问
    
    // 递归访问上下左右四个方向的相邻陆地
    dfs(grid, i-1, j) // 上
    dfs(grid, i+1, j) // 下
    dfs(grid, i, j-1) // 左
    dfs(grid, i, j+1) // 右
}

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

说明：Golang版本同样使用了DFS算法，但注意在Go中二维数组（切片）的传递和边界条件判断。

复杂度分析

时间复杂度：O(mn)，其中m和n分别是网格的行数和列数。因为我们需要遍历整个网格一次，并且在每个陆地上都执行DFS操作，DFS操作的时间复杂度取决于与当前陆地相连的其他陆地的数量，但最坏情况下会遍历完整个网格，因此总的时间复杂度是O(mn)。
空间复杂度：O(mn)（DFS栈空间）。在最坏的情况下，整个网格都是陆地，并且所有陆地都相互连接，此时DFS的递归调用栈会达到最大深度，即网格的面积mn。然而，在平均情况下，空间复杂度会远小于O(mn)，因为大多数DFS调用都会在遇到水域时返回。

方式二：使用广度优先搜索（BFS）

思路

与DFS类似，BFS也通过遍历网格来寻找岛屿。但BFS通常使用队列来存储待访问的节点（在这里是网格中的位置）。当一个陆地（‘1’）被访问时，我们将其标记为已访问（如’0’），并将其四个相邻的陆地（如果存在）加入队列中。我们继续从队列中取出节点，直到队列为空，这意味着我们已经探索了一个完整的岛屿。然后，我们重复这个过程，直到所有的陆地都被访问过。

代码实现

Java实现

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

public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int count = 0;
        int m = grid.length;
        int n = grid[0].length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    bfs(grid, i, j);
                }
            }
        }
        
        return count;
    }
    
    private void bfs(char[][] grid, int row, int col) {
        int m = grid.length;
        int n = grid[0].length;
        
        // 定义上下左右四个方向的偏移量
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        
        // 使用队列存储待访问的节点
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{row, col});
        
        // 标记当前节点为已访问
        grid[row][col] = '0';
        
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int x = curr[0];
            int y = curr[1];
            
            // 遍历四个方向
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                // 检查是否越界和是否为陆地且未访问
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == '1') {
                    // 标记为已访问并加入队列
                    grid[nx][ny] = '0';
                    queue.offer(new int[]{nx, ny});
                }
            }
        }
    }
}

C++实现

#include <queue>
#include <vector>

using namespace std;

void bfs(vector<vector<char>>& grid, int i, int j) {
    int m = grid.size();
    int n = grid[0].size();
    
    // 定义上下左右四个方向的偏移量
    vector<int> dx = {-1, 1, 0, 0};
    vector<int> dy = {0, 0, -1, 1};
    
    // 使用队列存储待访问的节点
    queue<pair<int, int>> q;
    q.push({i, j});
    
    // 标记当前节点为已访问
    grid[i][j] = '0';
    
    while (!q.empty()) {
        auto curr = q.front();
        q.pop();
        int x = curr.first;
        int y = curr.second;
        
        // 遍历四个方向
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            
            // 检查是否越界和是否为陆地且未访问
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == '1') {
                // 标记为已访问并加入队列
                grid[nx][ny] = '0';
                q.push({nx, ny});
            }
        }
    }
}

int numIslands(vector<vector<char>>& grid) {
    if (grid.empty()) return 0;
    int m = grid.size();
    int n = grid[0].size();
    int count = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                count++;
                bfs(grid, i, j);
            }
        }
    }
    
    return count;
}

Python3实现

from collections import deque

def bfs(grid, row, col):
    m, n = len(grid), len(grid[0])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 右，左，下，上
    queue = deque([(row, col)])
    grid[row][col] = 0  # 标记为已访问
    
    while queue:
        x, y = queue.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
                grid[nx][ny] = 0  # 标记为已访问
                queue.append((nx, ny))

def numIslands(grid):
    if not grid:
        return 0
    m, n = len(grid), len(grid[0])
    count = 0
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                count += 1
                bfs(grid, i, j)
    
    return count

Go实现

package main

import (
	"container/list"
)

type Point struct {
	X, Y int
}

func bfs(grid [][]byte, row, col int) {
	m, n := len(grid), len(grid[0])
	directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} // 上，下，左，右
	queue := list.New()
	queue.PushBack(Point{row, col})
	grid[row][col] = '0' // 标记为已访问
	
	for queue.Len() > 0 {
		curr := queue.Front().Value.(Point)
		queue.Remove(queue.Front())
		
		for _, dir := range directions {
			nx, ny := curr.X+dir[0], curr.

总结

方式	优点	缺点	时间复杂度	空间复杂度
DFS	实现简单，容易理解	在最坏情况下，空间复杂度较高	O(mn)	O(mn)（DFS栈空间）

相似题目

相似题目	难度	链接
LeetCode 695. 岛屿的最大面积	中等	LeetCode链接
LeetCode 130. 被围绕的区域	中等	LeetCode链接
[LeetCode 1254. 统计封闭岛屿的数目