DFS & BFS& 并查集 -leetcode-200. 岛屿数量

200. 岛屿数量

题目描述
DFS & BFS& 并查集 -leetcode-200. 岛屿数量

本题就是求 图中 连通分量的个数

求图中 连通分量个数的方法(3 种):

  • DFS
  • BFS
  • 并查集

DFS

使用标记数组

使用 visited 标记数组,保证图中每个顶点不会重复遍历

class Solution {
   // 上下左右 4 个方向
    int[] dirx = {-1, 1, 0, 0};
    int[] diry = {0, 0, -1, 1};
    // 全局变量
    int m;
    int n;
    char[][] grid;
    boolean[][] visited;

    public int numIslands(char[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        // 全局变量
        this.m = grid.length;
        this.n = grid[0].length;
        System.out.println("m = " + m);
        System.out.println("n = " + n);
        this.grid = grid;
        this.visited = new boolean[m][n];
        // visited[0][0] = true;
        int res = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    res++;
                    dfs(i, j);
                }
            }
        }
        return res;
    }

    public void dfs(int x, int y) {
        // 这里其实不用终止条件,因为下面 for 里面就会终止了
        // if (x < 0 || x >= n || y < 0 || y >= n) return;
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int xx = x + dirx[i];
            int yy = y + diry[i];
            // 保证 xx 和 yy 没有越界
            if (xx < 0 || xx >= m || yy < 0 || yy >= n) {
                continue;
            }
            // 不是岛屿(不是 1),则不遍历
            if (grid[xx][yy] == '0') {
                continue;
            }
            // 不能往回走
            if (visited[xx][yy]) {
                continue;
            }
            dfs(xx, yy);
            // 不用回溯,因为要统计 连通分量个数
        }
    }
}

DFS & BFS& 并查集 -leetcode-200. 岛屿数量

不使用标记数组

其实,本题不必要使用 visited 标记数组,直接利用 gird 数组本身 就可以实现“标记” (每个顶点遍历后,就修改为 '0'

class Solution {
   // 上下左右 4 个方向
    int[] dirx = {-1, 1, 0, 0};
    int[] diry = {0, 0, -1, 1};
    // 全局变量
    int m;
    int n;
    char[][] grid;

    public int numIslands(char[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        // 全局变量
        this.m = grid.length;
        this.n = grid[0].length;
        this.grid = grid;
        int res = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    dfs(i, j);
                }
            }
        }
        return res;
    }

    public void dfs(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int xx = x + dirx[i];
            int yy = y + diry[i];
            // 保证 xx 和 yy 没有越界,并且新地方 仍然是 “陆地”
            if (xx < 0 || xx >= m || yy < 0 || yy >= n || grid[xx][yy] == '0') {
                continue;
            }
            grid[xx][yy] = '0'; // 相当于 visited,这里 防止回头走
            dfs(xx, yy);
            // 不用回溯,因为要统计 连通分量个数
        }
    }
}

DFS & BFS& 并查集 -leetcode-200. 岛屿数量

BFS

类似 DFS,但是 BFS 要借助 队列实现

队列中存放的是值为 '1' 的节点,这里当然也可以 定义一个 class Node,里面有 x,y 两个字段,然后 队列 queue 里面存 Node 类型。

但是,这里可以很巧妙的做法是,将 (x, y) 转换为 x * n + y,然后 queue 里面存 x * n + y 就行

class Solution {
    // 上下左右 4 个方向
    int[] dirx = {-1, 1, 0, 0};
    int[] diry = {0, 0, -1, 1};
    // 全局变量
    int n;
    int m;
    char[][] grid;

    public int numIslands(char[][] grid) {
        // 全局变量
        this.m = grid.length;
        this.n = grid[0].length;
        this.grid = grid;
        int res = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    bfs(i, j);
                }
            }
        }
        return res;
    }
    
    public void bfs(int startx, int starty) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(startx * n + starty); // 这里当然也可以 勇哥 class Node,里面有 x,y 两个字段
        grid[startx][starty] = '0'; // 标记(否则,会往回走)
        while (!queue.isEmpty()) {
            int size = queue.size();
            // System.out.println(queue);
            // System.out.println("size = " + size);
            for (int i = 0; i < size; i++) { // 这个 for 可以不要,这里仅仅是为了看 bfs 的遍历情况
                int node = queue.poll(); // 取队列元素
                int oldx = node / n;
                int oldy = node % n;
                for (int j = 0; j < 4; j++) { // 找 上下左右 4 个方向的点是否符合条件
                    // 新的点
                    int xx = oldx + dirx[j];
                    int yy = oldy + diry[j];
                    // 保证 xx 和 yy 没有越界,并且 不会往回走(兜圈子)
                    if (xx < 0 || xx >= m || yy < 0 || yy >= n || grid[xx][yy] == '0') { // 逻辑短路,grid[xx][yy] == '0' 必须放最后
                        continue;
                    }
                    grid[xx][yy] = '0'; // 标记(这里不用 visited了,防止往回走)
                    queue.add(xx * n + yy);
                }
            }
        }
    }
}

DFS & BFS& 并查集 -leetcode-200. 岛屿数量

并查集

解决连通性,并查集是一把好手

思路:

  1. 将相邻的“陆地”(这里只用看 2 个方向(向下、向右))合并,即 union
  2. 统计 grid 中 “水”的个数 (grid[i][j] == ‘0’)waters
  3. 经过合并相邻“陆地”后 grid 中值为 '1' 的个数 count - 水的个数,就是 岛屿数量

注意:这里只用走两个方向(因为 外面还有两个 for )

public class Solution {
    // 下、右 2 个方向
    int[] dirx = {1, 0};
    int[] diry = {0, 1};
    // 全局变量
    int n;
    int m;
    char[][] grid;

    public int numIslands(char[][] grid) {
        // 全局变量
        this.m = grid.length;
        this.n = grid[0].length;
        System.out.println("m = " + m);
        System.out.println("n = " + n);
        this.grid = grid;
        int res = 0;

        int waters = 0; // 水 的数量
        UnionFindSet unionFindSet = new UnionFindSet(m * n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '0') {
                    waters++;
                } else { // 陆地
                    // 只用走两个方向(因为 外面还有两个 for )
                    for (int k = 0; k < 2; k++) {
                        int xx = i + dirx[k];
                        int yy = j + diry[k];
                        // 保证 xx 和 yy 没有越界,并且 新地方为陆地
                        if (xx < 0 || xx >= m || yy < 0 || yy >= n || grid[xx][yy] == '0') {
                            continue;
                        }
                        // System.out.println("-----------------");
                        unionFindSet.union(getIndex(i, j), getIndex(xx, yy));
                    }
                }
            }
        }
        return unionFindSet.getCount() - waters;
    }

    public int getIndex(int x, int y) {
        return x * n + y; // 不是 x * m + y
    }
}

/**
 * 并查集
 */
class UnionFindSet {
    /**
     * 存放当前节点的父亲节点,如果当前节点节点的父节点是自己,则表明该节点是所在集合的 根节点。
     * patent[i] 表示 i 的父节点
     */
    private int[] parent;
    /**
     * 用来计算连通分量的个数(连通分量个数:size - count)
     */
    private int count;

    public UnionFindSet(int size) {
        this.count = size;
        this.parent = new int[size];
        init(size);
    }

    /**
     * 返回 连通分量个数
     * @return
     */
    public int getCount() {
        return count;
    }

    /**
     * 给 parent 初始化
     * @param size parent 数组的大小
     */
    public void init(int size) {
        // 初始化(开始时,每个节点的父亲是自己,表明开始时 自己独立一个门派)
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    /**
     * 查找 x 所在集合的根节点 root(门派掌门人)
     * @param x
     * @return
     */
    public int find(int x) {
        int r = x;
        // 找 x 所在集合的 根节点。
        // patent[i] 表示 i 的父节点。如果当前节点节点的父节点是自己,则表明该节点是所在集合的 根节点。
        while (parent[r] != r) { // 找 门派掌门人
            r = parent[r];       // 接着找上街,直到找到 当前门派掌门人
        }
        return r; // 当前集合的 根节点,即门派掌门人
    }

    /**
     * 判断 x 和 y 是否属于同一个集合:
     *      如果是,则不做任何操作;
     *      否则,将 x 和 y 所在集合 合并(即,把 x 和 y 所在集合的 根节点连接即可)
     * @param x
     * @param y
     */
    public void union(int x, int y) {
        System.out.println("(" + x + ", " + y + ")");
        int fx = find(x);
        int fy = find(y);
        // 如果 x 和 y 不属于同一个集合(门派),则合并之
        if (fx != fy) {
            parent[fx] = fy; // 把 x 集合的 老大(掌门人)当了 y 集合掌门人的 小弟,这样两个集合(门派)就合并了
            // 每合并一次,更新 count
            count--;
        }
    }
}

DFS & BFS& 并查集 -leetcode-200. 岛屿数量

这里不该啊,应该是 并查集没有状态压缩

上一篇:机器学习笔记(十七)——非线性单层感知器


下一篇:云电脑直播简单指南