一、题目

　　1、审题

　　

　　2、分析

　　　　给出一个二维数组表示的字符集合，求出其中所有的由 1 组成的群体的个数，（想连续的 1 组成一个）。

 

 

二、解答

　　1、思路：

　　　　方法一、

　　　　 　  遍历数组中的每一个元素，将出现的值为 ‘1’ 的元素值改为 ’2‘，同时递归的将与此元素相连的值为 ‘1’的扩展元素值也改为 ‘ 2‘，此时，统计的群体值加 1。

　　　　　　最终，统计所有的群体值即可。

public int numIslands(char[][] grid) {                int result = 0;        int rows = grid.length;        if(rows == 0)            return 0;        int cols = grid[0].length;        for (int i = 0; i < rows; i++) {            for (int j = 0; j < cols; j++) {                if(grid[i][j] == '1') {                    result += 1;                    signAFlag(grid, rows, cols, i, j);                }            }        }                return result;    }        private void signAFlag(char[][] grid, int rows, int cols, int i, int j) {        if(grid[i][j] == '1')            grid[i][j] = '2';        else            return;        if(i - 1 >= 0)            signAFlag(grid, rows, cols, i - 1, j);        if(j - 1 >= 0)            signAFlag(grid, rows, cols, i, j - 1);        if(i + 1 < rows)            signAFlag(grid, rows, cols, i + 1, j);        if(j + 1 < cols)            signAFlag(grid, rows, cols, i, j + 1);    }

 

　　方法二、

　　　　采用并查集（UnionFind）。

class Solution {        int[][] distance = {
   {1, 0}, {-1, 0}, {0, 1}, {0, -1}};    public int numIslands(char[][] grid) {        if(grid == null || grid.length == 0 || grid[0].length == 0)            return 0;                int rows = grid.length;        int cols = grid[0].length;        UnionFind uf = new UnionFind(grid);        for (int i = 0; i < rows; i++) {            for (int j = 0; j < cols; j++) {                if(grid[i][j] == '1') {                    for(int[] d: distance) {                        int x = i + d[0];                        int y = j + d[1];                        if(x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == '1') {                            int id1 = i * cols + j;                            int id2 = x * cols + y;                            uf.union(id1, id2);                        }                    }                }            }                    }        return uf.count;    }}class UnionFind {        int[] father;    int m, n;    public int count = 0;    public UnionFind(char[][] grid) {        m = grid.length;        n = grid[0].length;        father = new int[m * n];                for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if(grid[i][j] == '1') {                    int id = i * n + j;                    father[id] = id;                    count++;                }            }        }    }        public void union(int node1, int node2) {        int find1 = find(node1);        int find2 = find(node2);        if(find1 != find2) {            father[find1] = find2;            count--;        }    }    public int find(int node) {        while(father[node] != node)            node = father[node];        return father[node];    }}