Leetcode200岛屿数量

题目分析

要区分二维矩阵中的每个1，需要将二维问题转化为一维编号问题。

如果矩阵有m列，位于第i行、第j列的元素对应的一维编号为i乘以m加j。

先将所有的1建成小集合，遍历矩阵，遇到1时，如果其左边或者上边有1则进行合并，最后统计并查集中集合的数量就是岛的数量。

代码求解

publicstaticintnumIslands(char[][]board){intn=board.length;intm=board[0].length;build(n,m,board);for(inti=0;i<n;i++){for(intj=0;j<m;j++){if(board[i][j]=='1'){if(j>0&&board[i][j-1]=='1'){union(i,j,i,j-1);}if(i>0&&board[i-1][j]=='1'){union(i,j,i-1,j);}}}}returnsets;}publicstaticintMAXSIZE=100001;publicstaticint[]father=newint[MAXSIZE];publicstaticintcols;publicstaticintsets;publicstaticvoidbuild(intn,intm,char[][]board){cols=m;sets=0;for(inta=0;a<n;a++){for(intb=0,index;b<m;b++){if(board[a][b]=='1'){index=index(a,b);father[index]=index;sets++;}}}}publicstaticintindex(inta,intb){returna*cols+b;}publicstaticintfind(inti){if(i!=father[i]){father[i]=find(father[i]);}returnfather[i];}publicstaticvoidunion(inta,intb,intc,intd){intfx=find(index(a,b));intfy=find(index(c,d));if(fx!=fy){father[fx]=fy;sets--;}}