力扣200岛屿数量解法3种

DFS BFS 并查集 三种方式解决岛屿问题

import java.util.*;
public class Edit {
    //并查集版本
    public int numIslandsUnion(char[][] grid) {
        UnionSet unionfind = new UnionSet(grid);
        //unionfind.UnionSet(grid);
        for(int clow=1;clow<unionfind.clow;clow++){
            if(grid[0][clow-1]=='1'&&grid[0][clow]=='1'){
                unionfind.union(0,clow,0,clow-1);
            }
        }
        for(int row=1;row<unionfind.row;row++){
            if(grid[row-1][0]=='1'&&grid[row][0]=='1'){
                unionfind.union(row,0,row-1,0);
            }
        }
        for(int row=1;row<unionfind.row;row++){
            for(int clow=1;clow<unionfind.clow;clow++){
                if(grid[row][clow-1]=='1'&&grid[row][clow]=='1'){
                    unionfind.union(row,clow,row,clow-1);
                }
                if(grid[row-1][clow]=='1'&&grid[row][clow]=='1'){
                    unionfind.union(row,clow,row-1,clow);
                }
            }
        }
        return unionfind.sets;
    }



    //bfs版本
    public int numIslandsBfs(char[][] grid) {
        Queue<int[]> que = new LinkedList<int[]>();
        int count=0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1'){
                    que.add(new int[]{i,j});
                    while(!que.isEmpty()){
                        int[] cur = que.poll();
                        int tempi= cur[0];
                        int tempj= cur[1];
                        if(tempi>=0&&tempj>=0&&tempj<grid[0].length&&tempi<grid.length&&grid[tempi][tempj]=='1'){
                            grid[tempi][tempj]='0';
                            que.add(new int[]{tempi+1,tempj});
                            que.add(new int[]{tempi-1,tempj});
                            que.add(new int[]{tempi,tempj+1});
                            que.add(new int[]{tempi,tempj-1});
                        }
                    }
                    count++;
                }

            }
        }
        return count;
    }

    //dfs版本
    public int numIslandsdfs(char[][] grid) {
        int count=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);
                    count++;
                }

            }
        }
        return count;
    }
    public void dfs(char[][] grid,int i,int j){
        if(i<0||j>=grid[0].length||i>=grid.length||j<0||grid[i][j]=='0'||grid[i][j]=='2'){
            return;
        }
        grid[i][j]='2';
        dfs(grid,i+1,j);
        dfs(grid,i-1,j);
        dfs(grid,i,j+1);
        dfs(grid,i,j-1);
        return;
    }
    //并查集方法
    public static class UnionSet{
        private int[] parents;//存父节点
        private int[] size;//存的大小
        private int[] help;//辅助数组，当作栈
        private int  clow;
        private int  row;
        private int  sets;

        //先初始化,values传入进来的数组
        public  UnionSet(char[][] values){
            sets=0;
            row = values.length;
            clow = values[0].length;
            int length = clow*row;
            parents = new int[length];//每个元素的负类
            size = new int[length];
            help = new int[length];
            for(int i=0;i<row;i++){
                for(int j=0;j<clow;j++){
                    int in =index(i,j);
                    if(values[i][j]=='1'){
                        parents[in]=in;
                        size[in]=1;
                        sets++;
                    }
                }
            }

        }
        public  int index(int x,int y){
            return x*clow+y;
        }
        //找寻当前节点的最上面的节点
        public int findHead(int cur){
            int index=0;
            //路径压缩，利用help数组存储，从当前节点cur访问到顶部节点所经过的节点
            //最后将所储存的节点的父节点全部设置为顶部节点，利用顶部节点来代表这个集合
            while(cur!=parents[cur]){
                help[index++]=cur;
                cur=parents[cur];
            }
            for (index--;index==0;index--){
                parents[help[index]]=cur;
            }
            return cur;
        }
        //判断是否是同一个集合
        public boolean isSameSet(int a,int b){
            //从a和b分别开始找顶部节点，若节点相同则认为在同一个集合，若不同则不在同一个集合
            return findHead(a)==findHead(b)?true:false;
        }
        //将a和b放入到一个集合当中
        public void union(int row1,int clow1 ,int row2,int clow2){
            int a = index(row1,clow1);
            int b = index(row2,clow2);
            int aHead=findHead(a);
            int bHead=findHead(b);
            if(aHead!=bHead){
                //将规模较小的集合插入大集合当中
                int asize = size[aHead];
                int bsize= size[bHead];
                int big= asize>=bsize?aHead:bHead;
                int small= asize<bsize?aHead:bHead;
                parents[small]=big;
                size[big]=asize+bsize;
                size[small]=0;
                sets--;
            }
        }

    }
    
}

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159