首页 > itarticle > leetcode(200) number of islands 解法

leetcode(200) number of islands 解法

admin 11月 29, 2020 0

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:

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

Output: 1

Example 2:

1
2
3
4
5
6
7
 
Input:
11000
11000
00100
00011

Output: 3

解法

典型的地图遍历题，这里可以通过BFS和DFS解题。

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
 
class  {
    public int numIslands(char[][] grid) {
        int res = 0;
        int[] dirx = {1, -1, 0, 0};
        int[] diry = {0, 0, 1, -1};
        for (int i = 0; i < grid.length; i++)
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    Queue<node> q = new LinkedList();
                    q.offer(new node(i, j));
                    while (!q.isEmpty()) {
                        node now = q.poll();
                        grid[now.x][now.y] = '0';
                        for (int ii = 0; ii < 4; ii++) {
                            int nextx = now.x + dirx[ii];
                            int nexty = now.y + diry[ii];
                            if (nextx >= 0 && nextx < grid.length && nexty >= 0 && nexty < grid[0].length) {
                                if (grid[nextx][nexty] == '1') {
                                    node next = new node(nextx, nexty);
                                    grid[next.x][next.y] = '0';
                                    q.offer(next);
                                }
                            }
                        }
                    }
                    res++;
                }
            }
        return res;
    }
}

class node {
    int x;
    int y;

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

特别注意需要再新点入队前将地图中的值置0以避免重复访问死循环！！！

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
 
class  {
    public int numIslands(char[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    DFS(grid, i, j);
                    res++;
                }
            }
        }
        return res;
    }

    void DFS(char[][] grid, int x, int y) {
        int[] dirx = {1, -1, 0, 0};
        int[] diry = {0, 0, 1, -1};
        if (grid[x][y] == '1') {
            grid[x][y] = 0;
            for (int i = 0; i < 4; i++) {
                int nextx = x + dirx[i];
                int nexty = y + diry[i];
                if (nextx >= 0 && nextx < grid.length && nexty >= 0 && nexty < grid[0].length) {
                    if (grid[nextx][nexty] == '1') {
                        DFS(grid, nextx, nexty);
                    }
                }
            }
        }
        return;
    }
}

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
42
43
44
45
46
47
48
49
50
51
 
class  {
    public int numIslands(char[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    DFS(grid, i, j);
                    res++;
                }
            }
        }
        return res;
    }

    void DFS(char[][] grid, int x, int y) {
        int[] dirx = {1, -1, 0, 0};
        int[] diry = {0, 0, 1, -1};
        Stack<node> s = new Stack<>();
        s.push(new node(x, y));
        grid[x][y] = '0';
        while (!s.isEmpty()) {
            node tmp = s.peek();
            int flag = 0;
            for (int i = 0; i < 4; i++) {
                int nextx = tmp.x + dirx[i];
                int nexty = tmp.y + diry[i];
                if (nextx >= 0 && nextx < grid.length && nexty >= 0 && nexty < grid[0].length) {
                    if (grid[nextx][nexty] == '1') {
                        grid[nextx][nexty] = '0';
                        s.push(new node(nextx, nexty));
                        flag = 1;
                    }
                }
            }
            if (flag == 0) {
                s.pop();
            }
        }
        return;
    }
}

class node {
    int x;
    int y;

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

同样注意标0的时机。

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能