题目

题目地址： https://leetcode-cn.com/problems/number-of-islands/

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

示例1：

1
2
3
4
5
6
7
输入:
11110
11010
11000
00000

输出: 1

示例2：

1
2
3
4
5
6
7
输入:
11000
11000
00100
00011

输出: 3

答案

使用广度优先搜索算法(BFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
package com.jarome.leetcode;

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

public class SolutionIsland {

    public int numIslands(char[][] grid) {
        int islandSize = 0;
        int ySize = grid.length;
        // 遍历grid数组
        for (int i = 0; i < ySize; i++) {
            char[] item = grid[i];
            int xSize = item.length;
            for (int j = 0; j < xSize; j++) {
                char itemValue = item[j];
                if (itemValue != '1') {
                    // 当前不为1，直接跳过
                    continue;
                }
                // 岛屿数加1
                islandSize++;
                // 将当前标记为已处理
                grid[i][j] = '0';
                // 队列，用于进行广度搜索
                Queue<Point> queue = new LinkedList<Point>();
                Point start = new Point(j, i);
                queue.add(start);
                while (!queue.isEmpty()) {
                    // 移除当前
                    Point remove = queue.remove();
                    int x = remove.getX();
                    int y = remove.getY();
                    // 分别计算上下左右
                    // 上
                    deal(queue, grid, x, y - 1, xSize, ySize);
                    // 下
                    deal(queue, grid, x, y + 1, xSize, ySize);
                    // 左
                    deal(queue, grid, x - 1, y, xSize, ySize);
                    // 右
                    deal(queue, grid, x + 1, y, xSize, ySize);

                }
            }
        }
        return islandSize;
    }

    private void deal(Queue<Point> queue, char[][] grid, int x, int y, int xSize, int ySize) {
        if ((x >= 0 && x < xSize) && (y >= 0 && y < ySize) && grid[y][x] == '1') {
            grid[y][x] = '0';
            Point next = new Point(x, y);
            queue.add(next);
        }
    }

    static class Point {
        private int x;
        private int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public void setX(int x) {
            this.x = x;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }
    }

}

运行情况：

  • 执行时间：6ms
  • 内存消耗：42.6MB

分析：

  • 时间复杂度：O(M×N)，其中 M 和 N 分别为行数和列数。
  • 空间复杂度：O(min(M,N))，在最坏的情况下（全部为陆地），队列的大小可以达到 min(M，N)。

使用深度优先搜索算法(DFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package com.jarome.leetcode;

public class SolutionIslandDFS {
    public int numIslands(char[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            char[] row = grid[i];
            for (int j = 0; j < row.length; j++) {
                char c = grid[i][j];
                if (c == '1') {
                    res++;
                    island(i, j, grid);
                }
            }
        }
        return res;
    }

    private void island(int i, int j, char[][] grid) {
        int ySize = grid.length;
        int xSize = grid[0].length;
        if (i < 0 || i >= ySize || j < 0 || j >= xSize) {
            // 有一个超出边界，返回true
            return;
        }
        char c = grid[i][j];
        if (c == '0') {
            return;
        }
        grid[i][j] = '0';
        // 分别处理四个方向
        // 上
        island(i, j - 1, grid);
        // 下
        island(i, j + 1, grid);
        // 左
        island(i - 1, j, grid);
        // 右
        island(i + 1, j, grid);
    }
}

运行情况：

  • 执行时间：2ms
  • 内存消耗：42.3 MB