力扣图论篇

以下思路来自代码随想录以及官方题解。

797.所有可能的路径

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

class Solution {

    // 存储所有路径的结果
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    // 用于深度优先搜索的栈
    Deque<Integer> stack = new ArrayDeque<Integer>();

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        // 将起始节点0加入栈中
        stack.offerLast(0);
        // 从起始节点0开始进行深度优先搜索，目标节点为graph.length - 1
        dfs(graph, 0, graph.length - 1);
        // 返回所有路径的结果
        return ans;
    }

    public void dfs(int[][] graph, int x, int n) {
        // 如果当前节点x等于目标节点n，说明找到了一条路径
        if (x == n) {
            // 将当前栈中的路径添加到结果列表中
            ans.add(new ArrayList<Integer>(stack));
            // 返回上一层递归
            return;
        }

        // 遍历当前节点x的所有邻居节点y
        for (int y : graph[x]) {
            // 将邻居节点y加入栈中
            stack.offerLast(y);
            // 从邻居节点y开始继续进行深度优先搜索
            dfs(graph, y, n);
            // 回溯：将邻居节点y从栈中移除
            stack.pollLast();
        }
    }
}

200.岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

class Solution {

    // 深度优先搜索函数，用于遍历岛屿
    public void dfs(char[][] grid, int r, int c) {
        int nr = grid.length; // 获取行数
        int nc = grid[0].length; // 获取列数

        // 如果越界或者当前位置不是岛屿，直接返回
        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }

        // 将当前位置标记为已访问
        grid[r][c] = '0';
        // 向上、下、左、右四个方向进行深度优先搜索
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    // 计算岛屿数量的函数
    public int numIslands(char[][] grid) {
        // 如果输入为空或者没有元素，直接返回0
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int nr = grid.length; // 获取行数
        int nc = grid[0].length; // 获取列数
        int num_idlands = 0; // 初始化岛屿数量为0
        // 遍历整个网格
        for (int r = 0; r < nr; r++) {
            for (int c = 0; c < nc; c++) {
                // 如果当前位置是岛屿（值为'1'）
                if (grid[r][c] == '1') {
                    num_idlands++; // 岛屿数量加1
                    dfs(grid, r, c); // 从当前位置开始进行深度优先搜索，将相邻的岛屿都标记为已访问
                }
            }
        }

        return num_idlands; // 返回岛屿数量
    }
}

130.被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 ‘O’ 用 'X' 填充。

输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

输入：board = [["X"]]
输出：[["X"]]

1020.飞地的数量

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻**（上、下、左、右）**的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。

输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：所有 1 都在边界上或可以到达边界。

这道题是官方题解

class Solution {

    // 定义四个方向的偏移量
    public static int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    private int m, n; // 行数和列数
    private boolean[][] visited; // 记录是否访问过

    public int numEnclaves(int[][] grid) {
        m = grid.length; // 获取行数
        n = grid[0].length; // 获取列数
        visited = new boolean[m][n]; // 初始化访问数组

        // 遍历第一列和最后一列
        for (int i = 0; i < m; i++) {
            dfs(grid, i, 0); // 深度优先搜索第一列
            dfs(grid, i, n - 1); // 深度优先搜索最后一列
        }

        // 遍历第一行和最后一行（不包括第一列和最后一列）
        for (int j = 1; j < n - 1; j++) {
            dfs(grid, 0, j); // 深度优先搜索第一行
            dfs(grid, m - 1, j); // 深度优先搜索最后一行
        }

        int count = 0; // 记录未被访问过的陆地数量
        // 遍历除第一行、最后一行、第一列、最后一列之外的区域
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) { // 如果当前位置是陆地且未被访问过
                    count++; // 计数器加一
                }
            }
        }

        return count; // 返回未被访问过的陆地数量
    }

    // 深度优先搜索函数
    public void dfs(int[][] grid, int row, int col) {
        // 如果越界或者当前位置是水域或者已经访问过，直接返回
        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0 || visited[row][col]) {
            return;
        }
        visited[row][col] = true; // 标记当前位置已访问
        // 遍历四个方向进行深度优先搜索
        for (int[] dir : dirs) {
            dfs(grid, row + dir[0], col + dir[1]);
        }
    }
}