HOT100-哈希汇总

HOT100 图论

1.岛屿数量

链接：200. 岛屿数量 - 力扣（LeetCode）

代码：

法1：DFS：其实就是找连通图的个数

class Solution {
    // m 表示行数，n 表示列数
    int m, n;

    public int numIslands(char[][] grid) {
        // 如果网格为空，直接返回 0
        if (grid.length == 0) {
            return 0;
        }

        // 获取网格的行数和列数
        m = grid.length;
        n = grid[0].length;

        // 记录岛屿数量
        int ans = 0;

        // 遍历整个二维网格
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {

                // 如果当前位置是陆地 '1'
                // 说明发现了一座新的岛屿
                if (grid[i][j] == '1') {

                    // 从当前位置开始 DFS，
                    // 把和它相连的所有陆地都标记为已访问
                    dfs(grid, i, j);

                    // 一次 DFS 会处理完一整座岛屿
                    // 所以岛屿数量加 1
                    ++ans;
                }
            }
        }

        // 返回岛屿总数
        return ans;
    }

    /**
     * 从坐标 (i, j) 开始进行深度优先搜索
     * 作用：
     * 把当前陆地以及上下左右相连的所有陆地都标记为已访问
     */
    private void dfs(char[][] grid, int i, int j) {
        // 递归终止条件：
        // 1. i < 0：越过上边界
        // 2. i == m：越过下边界
        // 3. j < 0：越过左边界
        // 4. j == n：越过右边界
        // 5. grid[i][j] == '6'：当前位置已经访问过
        // 6. grid[i][j] == '0'：当前位置是水域
        if (i < 0 || i == m || j < 0 || j == n
                || grid[i][j] == '6'
                || grid[i][j] == '0') {
            return;
        }

        // 将当前陆地标记为已访问
        // 这里用 '6' 表示已经访问过，避免重复搜索
        grid[i][j] = '6';

        // 向上搜索
        dfs(grid, i - 1, j);

        // 向下搜索
        dfs(grid, i + 1, j);

        // 向左搜索
        dfs(grid, i, j - 1);

        // 向右搜索
        dfs(grid, i, j + 1);
    }
}

法2：BFS

class Solution {
    int m, n;

    public int numIslands(char[][] grid) {
        if (grid.length == 0) {
            return 0;
        }

        m = grid.length;
        n = grid[0].length;

        int ans = 0;

        // 四个方向：上、下、左、右
        int[][] dirs = {
                { -1, 0 },
                { 1, 0 },
                { 0, -1 },
                { 0, 1 }
        };

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {

                // 遇到未访问过的陆地，说明发现一座新岛屿
                if (grid[i][j] == '1') {
                    ans++;

                    // 使用队列进行 BFS
                    Queue<int[]> queue = new LinkedList<>();

                    // 先把当前点加入队列
                    queue.offer(new int[] { i, j });

                    // 标记为已访问，避免重复加入队列
                    grid[i][j] = '0';

                    while (!queue.isEmpty()) {
                        int[] cur = queue.poll();
                        int x = cur[0];
                        int y = cur[1];

                        // 遍历上下左右四个方向
                        for (int[] dir : dirs) {
                            int nx = x + dir[0];
                            int ny = y + dir[1];

                            // 判断是否越界
                            if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
                                continue;
                            }

                            // 如果是陆地，就加入队列继续扩展
                            if (grid[nx][ny] == '1') {
                                queue.offer(new int[] { nx, ny });

                                // 标记为已访问
                                grid[nx][ny] = '0';
                            }
                        }
                    }
                }
            }
        }

        return ans;
    }
}

法3：栈DFS

class Solution {
    int m, n;

    public int numIslands(char[][] grid) {
        if (grid.length == 0) {
            return 0;
        }

        m = grid.length;
        n = grid[0].length;

        int ans = 0;

        int[][] dirs = {
                { -1, 0 },
                { 1, 0 },
                { 0, -1 },
                { 0, 1 }
        };

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {

                if (grid[i][j] == '1') {
                    ans++;

                    // 使用栈模拟递归 DFS
                    Deque<int[]> stack = new ArrayDeque<>();
                    stack.push(new int[] { i, j });

                    // 标记为已访问
                    grid[i][j] = '0';

                    while (!stack.isEmpty()) {
                        int[] cur = stack.pop();
                        int x = cur[0];
                        int y = cur[1];

                        for (int[] dir : dirs) {
                            int nx = x + dir[0];
                            int ny = y + dir[1];

                            if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
                                continue;
                            }

                            if (grid[nx][ny] == '1') {
                                stack.push(new int[] { nx, ny });
                                grid[nx][ny] = '0';
                            }
                        }
                    }
                }
            }
        }

        return ans;
    }
}

法4：并查集