广州专业网站设计公司,网站注册搜索引擎的目的,百度网站的建设,短网址api接口797. 所有可能的路径
题目:
给你一个有 n 个节点的 有向无环图#xff08;DAG#xff09;#xff0c;请你找出所有从节点 0 到节点 n-1 的路径并输出#xff08;不要求按特定顺序#xff09;
graph[i] 是一个从节点 i 可以访问的所有节点的列表#xff08;即从节点 i …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 {ListListInteger res;ListInteger list;public ListListInteger allPathsSourceTarget(int[][] graph) {res new ArrayList();list new LinkedList();list.add(0);deal(graph,0);return res;}//回溯:深度优先遍历void deal(int[][] graph,int node){if(nodegraph.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 i0;im;i){for(int j0;jn;j){if(grid[i][j]1){res;deal(grid,i,j);//将遍历过的陆地—水}}}return res;}void deal(char[][] grid,int i,int j){if(i0 || im || j0 || jn || grid[i][j]0){return;}grid[i][j] 0;for(int[] dir : dirs){deal(grid,idir[0],jdir[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 i0;im;i){for(int j0;jn;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(i0 || im || j0 || jn || grid[i][j]0){return;}grid[i][j] 0;count;for(int[] dir : dirs){deal(grid,idir[0],jdir[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 i0;im;i){deal(grid,i,0);deal(grid,i,n-1);}for(int j0;jn;j){deal(grid,0,j);deal(grid,m-1,j);}int res 0;for(int i1;im-1;i){for(int j1;jn-1;j){if(grid[i][j]1){res;}}}return res;}void deal(int[][] grid,int i,int j){if(i0 || im || j0 || jn || grid[i][j]0){return;}grid[i][j] 0;for(int[] dir : dirs){deal(grid,idir[0],jdir[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 i0;im;i){deal(board,i,0);deal(board,i,n-1);}for(int j0;jn;j){deal(board,0,j);deal(board,m-1,j);}for(int i0;im;i){for(int j0;jn;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(i0 || im || j0 || jn || board[i][j]!O){return;}board[i][j] A;for(int[] dir : dirs){deal(board,idir[0],jdir[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(ListListInteger rooms) {boolean[] visited new boolean[rooms.size()];QueueInteger 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 i0;im;i){for(int j0;jn;j){if(grid[i][j]1){for(int[] dir : dirs){int p i dir[0];int q j dir[1];if(p0 || pm || q0 || qn || grid[p][q]0){res;}}}}}return res;}
}
