图论-算法题

797. 所有可能的路径

题目:

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

示例 1：

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

示例 2：

输入：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>> res;List<Integer> list;public List<List<Integer>> allPathsSourceTarget(int[][] graph) {res = new ArrayList();list = new LinkedList();list.add(0);deal(graph,0);return res;}//回溯:深度优先遍历void deal(int[][] graph,int node){if(node==graph.length-1){res.add(new ArrayList(list));}for(int num : graph[node]){list.add(num);deal(graph,num);list.removeLast();}}
}

200. 岛屿数量

题目

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

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

示例 2：

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

答案

class Solution {int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};int m,n;public int numIslands(char[][] grid) {m = grid.length;n = grid[0].length;int res = 0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]=='1'){res++;deal(grid,i,j);//将遍历过的陆地—>水}}}return res;}void deal(char[][] grid,int i,int j){if(i<0 || i>=m || j<0 || j>=n || grid[i][j]=='0'){return;}grid[i][j] = '0';for(int[] dir : dirs){deal(grid,i+dir[0],j+dir[1]);}}
}

695. 岛屿的最大面积

题目

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

示例 2：

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

答案

class Solution {int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};int m,n;int count;public int maxAreaOfIsland(int[][] grid) {m = grid.length;n = grid[0].length;int res = 0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){count = 0;deal(grid,i,j);res = Math.max(res,count);}}}return res;}void deal(int[][] grid,int i,int j){if(i<0 || i>=m || j<0 || j>=n || grid[i][j]==0){return;}grid[i][j] = 0;count++;for(int[] dir : dirs){deal(grid,i+dir[0],j+dir[1]);}}
}

1020. 飞地的数量

题目

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

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

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

示例 1：

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

示例 2：

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

答案

class Solution {int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};int m,n;public int numEnclaves(int[][] grid) {m = grid.length;n = grid[0].length;for(int i=0;i<m;i++){deal(grid,i,0);deal(grid,i,n-1);}for(int j=0;j<n;j++){deal(grid,0,j);deal(grid,m-1,j);}int res = 0;for(int i=1;i<m-1;i++){for(int j=1;j<n-1;j++){if(grid[i][j]==1){res++;}}}return res;}void deal(int[][] grid,int i,int j){if(i<0 || i>=m || j<0 || j>=n || grid[i][j]==0){return;}grid[i][j] = 0;for(int[] dir : dirs){deal(grid,i+dir[0],j+dir[1]);}}
}

130. 被围绕的区域

题目

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

示例 1：

输入：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'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 2：

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

答案

class Solution {int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};int m,n;public void solve(char[][] board) {m = board.length;n = board[0].length;for(int i=0;i<m;i++){deal(board,i,0);deal(board,i,n-1);}for(int j=0;j<n;j++){deal(board,0,j);deal(board,m-1,j);}for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(board[i][j]=='A'){board[i][j] = 'O';}else if(board[i][j]=='O'){board[i][j] ='X';}}}}void deal(char[][] board,int i,int j){if(i<0 || i>=m || j<0 || j>=n || board[i][j]!='O'){return;}board[i][j] = 'A';for(int[] dir : dirs){deal(board,i+dir[0],j+dir[1]);}}
}

841. 钥匙和房间

题目

有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。

当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。

给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。

示例 1：

输入：rooms = [[1],[2],[3],[]]
输出：true
解释：
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。

示例 2：

输入：rooms = [[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。

答案

class Solution {public boolean canVisitAllRooms(List<List<Integer>> rooms) {boolean[] visited = new boolean[rooms.size()];Queue<Integer> queue = new LinkedList();queue.offer(0);visited[0] = true;//注意这个while(!queue.isEmpty()){int curr = queue.poll();for(int index : rooms.get(curr)){if(!visited[index]){visited[index] = true;queue.offer(index);}}}for(boolean flag : visited){if(!flag){return false;}}return true;}
}

463. 岛屿的周长

题目

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例 1：

输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边

示例 2：

输入：grid = [[1]]
输出：4

示例 3：

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

答案

class Solution {int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};int m,n;public int islandPerimeter(int[][] grid) {m = grid.length;n = grid[0].length;int res = 0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){for(int[] dir : dirs){int p = i + dir[0];int q = j + dir[1];if(p<0 || p>=m || q<0 || q>=n || grid[p][q]==0){res++;}}}}}return res;}
}