代码随想录——图论一刷day02

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

`

---

一、力扣695. 岛屿的最大面积

淹没岛屿的递归

class Solution {
    int[][] move = {
            {0,1},
            {0,-1},
            {-1,0},
            {1,0}
    };
    int count = 0;
    public int maxAreaOfIsland(int[][] grid) {
        
        int res = 0;
        for(int i = 0; i < grid.length; i ++){
            for(int j = 0; j < grid[i].length; j ++){
                if(grid[i][j] == 1){
                    count = 1;
                    dfs(grid, i , j);
                    res = Math.max(count, res);
                }
            }
        }
        return res;
    }
    public void dfs(int[][] grid, int x, int y){
        grid[x][y] = 0;
        for(int i = 0; i < 4; i ++){
            int nextX = x + move[i][0];
            int nextY = y + move[i][1];
            if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[x].length ||             grid[nextX][nextY] == 0){
                continue;
            }
            count ++;
            dfs(grid, nextX, nextY);
        }
    }
}
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

使用标记数组的递归

class Solution {
    int[][] move = {
            {0,1},
            {0,-1},
            {-1,0},
            {1,0}
    };
    boolean[][] flag;
    int count = 0;
    public int maxAreaOfIsland(int[][] grid) {
        flag = new boolean[grid.length][grid[0].length];
        int res = 0;
        for(int i = 0; i < grid.length; i ++){
            for(int j = 0; j < grid[i].length; j ++){
                if(grid[i][j] == 1 && flag[i][j] == false){
                    count = 1;
                    dfs(grid, i , j);
                    res = Math.max(count, res);
                }
            }
        }
        return res;
    }
    public void dfs(int[][] grid, int x, int y){
        flag[x][y] = true;
        for(int i = 0; i < 4; i ++){
            int nextX = x + move[i][0];
            int nextY = y + move[i][1];
            if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[x].length ||             grid[nextX][nextY] == 0 || flag[nextX][nextY] == true){
                continue;
            }
            count ++;
            dfs(grid, nextX, nextY);
        }
    }
}
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

广度优先搜索

class Solution {
    int[][] move = {
        {0,1},
        {0,-1},
        {-1,0},
        {1,0}
    };
    int count = 0;
    boolean[][] flag;
    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        flag = new boolean[grid.length][grid[0].length];
        for(int i = 0; i < grid.length; i ++){
            for(int j = 0; j < grid[i].length; j ++){
                if(grid[i][j] == 1 && flag[i][j] == false){
                    count = 1;
                    bfs(grid, i, j);
                    res = Math.max(res, count);
                }
            }
        }
        return res;
    }
    public void bfs(int[][] grid, int x, int y){
        Deque<int[]> deq = new LinkedList<>();
        flag[x][y] = true;
        deq.offerLast(new int[]{x, y});
        while(!deq.isEmpty()){
            int[] cur = deq.pollFirst();
            for(int i = 0; i < 4; i ++){
                int nextX = cur[0] + move[i][0];
                int nextY = cur[1] + move[i][1];
                if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[x].length || grid[nextX][nextY] == 0 || flag[nextX][nextY] == true){
                    continue;
                }
                count ++;
                flag[nextX][nextY] = true;
                deq.offerLast(new int[]{nextX, nextY});
            }
        }
    }
}
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

二、力扣1020. 飞地的数量

DFS淹没岛屿同时一边统计边界岛屿的陆地面积， 一边统计总陆地面积，最后返回差值

class Solution {
    int count = 0;
    int[][] move = {
        {0,1},
        {0,-1},
        {-1,0},
        {1,0}
    };
    boolean tag = false;
    public int numEnclaves(int[][] grid) {
        int res = 0;
        int edge = 0;
        for(int i = 0; i < grid.length; i ++){
            for(int j = 0; j < grid[i].length; j ++){
                if(grid[i][j] == 1){
                    count = 1;
                    dfs(grid, i, j);
                    if(tag == true){
                        edge += count;
                        tag = false;
                    }
                    res += count;
                }
            }
        }
        return res - edge;
    }
    public void dfs(int[][] grid, int x, int y){
        grid[x][y] = 0;
        for(int i = 0; i < 4; i ++){
            int nextX = move[i][0] + x;
            int nextY = move[i][1] + y;
            if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[x].length){
                tag = true;
            }
            if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[x].length || grid[nextX][nextY] == 0){
                continue;
            }
            count ++;
            dfs(grid, nextX, nextY);
        }
    }
}
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

DFS使用标记数组同时一边统计边界岛屿的陆地面积， 一边统计总陆地面积，最后返回差值

class Solution {
    int count = 0;
    int[][] move = {
        {0,1},
        {0,-1},
        {-1,0},
        {1,0}
    };
    boolean[][] flag;
    boolean tag = false;
    public int numEnclaves(int[][] grid) {
        flag = new boolean[grid.length][grid[0].length];
        int res = 0;
        int edge = 0;
        for(int i = 0; i < grid.length; i ++){
            for(int j = 0; j < grid[i].length; j ++){
                if(grid[i][j] == 1 && flag[i][j] == false){
                    count = 1;
                    dfs(grid, i, j);
                    if(tag == true){
                        edge += count;
                        tag = false;
                    }
                    res += count;
                }
            }
        }
        return res - edge;
    }
    public void dfs(int[][] grid, int x, int y){
        flag[x][y] = true;
        for(int i = 0; i < 4; i ++){
            int nextX = move[i][0] + x;
            int nextY = move[i][1] + y;
            if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[x].length){
                tag = true;
            }
            if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[x].length || grid[nextX][nextY] == 0 || flag[nextX][nextY] == true){
                continue;
            }
            count ++;
            dfs(grid, nextX, nextY);
        }
    }
}
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

BFS使用标记数组同时一边统计边界岛屿的陆地面积， 一边统计总陆地面积，最后返回差值

class Solution {
    int count = 0;
    int[][] move = {
        {0,1},
        {0,-1},
        {-1,0},
        {1,0}
    };
    boolean[][] flag;
    boolean tag = false;
    public int numEnclaves(int[][] grid) {
        flag = new boolean[grid.length][grid[0].length];
        int res = 0;
        int edge = 0;
        for(int i = 0; i < grid.length; i ++){
            for(int j = 0; j < grid[i].length; j ++){
                if(grid[i][j] == 1 && flag[i][j] == false){
                    count = 1;
                    bfs(grid, i, j);
                    if(tag == true){
                        edge += count;
                        tag = false;
                    }
                    res += count;
                }
            }
        }
        return res - edge;
    }
    public void bfs(int[][] grid, int x, int y){
        flag[x][y] = true;
        Deque<int[]> deq = new LinkedList<>();
        deq.offerLast(new int[]{x,y});
        while(!deq.isEmpty()){
            int[] cur = deq.pollFirst();
            for(int i = 0; i < 4; i ++){
                int nextX = move[i][0] + cur[0];
                int nextY = move[i][1] + cur[1];
                if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[x].length){
                    tag = true;
                }
                if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[x].length || grid[nextX][nextY] == 0 || flag[nextX][nextY] == true){
                    continue;
                }
                count ++;
                flag[nextX][nextY] = true;
                deq.offerLast(new int[]{nextX,nextY});
            }
        } 
    }
}
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

三、力扣1254. 统计封闭岛屿的数目

class Solution {
    int[][] move = {
        {1,0},
        {-1,0},
        {0,1},
        {0,-1}
    };
    public int closedIsland(int[][] grid) {
        int res = 0;
        for(int i = 0; i < grid.length; i ++){
            if(grid[i][0] == 0){
                dfs(grid, i, 0);
            }
            if(grid[i][grid[0].length-1] == 0){
                dfs(grid, i, grid[0].length-1);
            }
        }
        for(int i = 0; i < grid[0].length; i ++){
            if(grid[0][i] == 0){
                dfs(grid, 0, i);
            }
            if(grid[grid.length-1][i] == 0){
                dfs(grid, grid.length-1, i);
            }
        }
        for(int i = 0; i < grid.length; i ++){
            for(int j = 0; j < grid[0].length; j ++){
                if(grid[i][j] == 0){
                    res ++;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }
    public void dfs(int[][] grid, int x, int y){
        grid[x][y] = 1;
        for(int i = 0; i < 4; i ++){
            int nextX = move[i][0] + x;
            int nextY = move[i][1] + y;
            if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[x].length || grid[nextX][nextY] == 1){
                continue;
            }
            dfs(grid, nextX, nextY);
        }
    }
}
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