力扣图论篇

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

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 - 1dfs(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的所有邻居节点yfor (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) {// 如果输入为空或者没有元素，直接返回0if (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++; // 岛屿数量加1dfs(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]);}}
}