不侵权的图片素材网站,烟台网络推广公司,wordpress编辑器汉,昆明网站建设去出发科技公司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]]
示例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]]
// dfs
class Solution {ListListInteger list new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger allPathsSourceTarget(int[][] graph) {path.add(0);dfs(graph, 0);return list;}public void dfs(int[][] graph, int node){if(node graph.length - 1){list.add(new ArrayList(path));return;}for(int i 0; i graph[node].length; i){path.add(graph[node][i]);dfs(graph, graph[node][i]);path.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// dfs
class Solution {public int numIslands(char[][] grid) {int count 0;for(int i 0; i grid.length; i){for(int j 0; j grid[0].length; j){if(grid[i][j] 1){count;dfs(grid, i, j);}}}return count;}public void dfs(char[][] grid, int i, int j){if(i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0){return;}grid[i][j] 0;dfs(grid, i - 1, j);dfs(grid, i 1, j);dfs(grid, i, j - 1);dfs(grid, i, j 1);}
}
// bfs
class Solution {public int numIslands(char[][] grid) {int count 0;for(int i 0; i grid.length; i){for(int j 0; j grid[0].length; j){if(grid[i][j] 1){count;bfs(grid, i, j);}}}return count;}public void bfs(char[][] grid, int i, int j){Queueint[] queue new LinkedList();queue.offer(new int[]{i, j});while(!queue.isEmpty()){int[] cur queue.poll();i cur[0];j cur[1];if(i 0 i grid.length j 0 j grid[0].length grid[i][j] 1){grid[i][j] 0;queue.offer(new int[]{i - 1, j});queue.offer(new int[]{i 1, j});queue.offer(new int[]{i, j - 1});queue.offer(new int[]{i, j 1});}}}
}
695. 岛屿的最大面积
给你一个大小为 m x n 的二进制矩阵 grid 。岛屿 是由一些相邻的 1 (代表土地) 构成的组合这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0代表水包围着。岛屿的面积是岛上值为 1 的单元格的数目。计算并返回 grid 中最大的岛屿面积。如果没有岛屿则返回面积为 0 。 输入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
// dfs
class Solution {int area;public int maxAreaOfIsland(int[][] grid) {int maxArea 0;for(int i 0; i grid.length; i){for(int j 0; j grid[0].length; j){if(grid[i][j] 1){area 0;dfs(grid, i, j);maxArea Math.max(maxArea, area);}}}return maxArea;}public void dfs(int[][] grid, int i, int j){if(i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0){return;}area;grid[i][j] 0;dfs(grid, i - 1, j);dfs(grid, i 1, j);dfs(grid, i, j - 1);dfs(grid, i, j 1);}
}
// bfs
class Solution {int area;public int maxAreaOfIsland(int[][] grid) {int maxArea 0;for(int i 0; i grid.length; i){for(int j 0; j grid[0].length; j){if(grid[i][j] 1){area 0;bfs(grid, i, j);maxArea Math.max(maxArea, area);}}}return maxArea;}public void bfs(int[][] grid, int i, int j){Queueint[] queue new LinkedList();queue.offer(new int[]{i, j});while(!queue.isEmpty()){int[] cur queue.poll();i cur[0];j cur[1];if(i 0 i grid.length j 0 j grid[0].length grid[i][j] 1){area;grid[i][j] 0;queue.offer(new int[]{i - 1, j});queue.offer(new int[]{i 1, j});queue.offer(new int[]{i, j - 1});queue.offer(new int[]{i, j 1});}}}
}
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
// dfs
class Solution {public int numEnclaves(int[][] grid) {for(int i 0; i grid.length; i){ if(grid[i][0] 1){ // 左侧dfs(grid, i, 0);}if(grid[i][grid[0].length - 1] 1){ // 右侧dfs(grid, i, grid[0].length - 1);}}for(int j 1; j grid[0].length - 1; j){ if(grid[0][j] 1){ // 上侧dfs(grid, 0, j);}if(grid[grid.length - 1][j] 1){ // 下侧dfs(grid, grid.length - 1, j);}}int count 0;for(int i 0; i grid.length; i){for(int j 0; j grid[0].length; j){if(grid[i][j] 1){count;}}}return count;}public void dfs(int[][] grid, int i, int j){if(i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0){return;}grid[i][j] 0;dfs(grid, i - 1, j);dfs(grid, i 1, j);dfs(grid, i, j - 1);dfs(grid, i, j 1);}
}
// bfs
class Solution {public int numEnclaves(int[][] grid) {for(int i 0; i grid.length; i){if(grid[i][0] 1){ // 左侧bfs(grid, i, 0);}if(grid[i][grid[0].length - 1] 1){ // 右侧bfs(grid, i, grid[0].length - 1);}}for(int j 1; j grid[0].length - 1; j){if(grid[0][j] 1){ // 上侧bfs(grid, 0, j);}if(grid[grid.length - 1][j] 1){ // 下侧bfs(grid, grid.length - 1, j);}}int count 0;for(int i 0; i grid.length; i){for(int j 0; j grid[0].length; j){if(grid[i][j] 1){count;}}}return count;}public void bfs(int[][] grid, int i, int j){Queueint[] queue new LinkedList();queue.offer(new int[]{i, j});while(!queue.isEmpty()){int[] cur queue.poll();i cur[0];j cur[1];if(i 0 i grid.length j 0 j grid[0].length grid[i][j] 1){grid[i][j] 0;queue.offer(new int[]{i - 1, j});queue.offer(new int[]{i 1, j});queue.offer(new int[]{i, j - 1});queue.offer(new int[]{i, j 1});}}}
}
130. 被围绕的区域
给你一个 m x n 的矩阵 board 由若干字符 X 和 O 找到所有被 X 围绕的区域并将这些区域里所有的 O 用 X 填充。 // dfs
class Solution {public void solve(char[][] board) {for(int i 0; i board.length; i){if(board[i][0] O){dfs(board, i, 0);}if(board[i][board[0].length - 1] O){dfs(board, i, board[0].length - 1);}}for(int j 1; j board[0].length - 1; j){if(board[0][j] O){dfs(board, 0, j);}if(board[board.length - 1][j] O){dfs(board, board.length - 1, j);}}for(int i 0; i board.length; i){for(int j 0; j board[0].length; j){if(board[i][j] A){board[i][j] O;}else if(board[i][j] O){board[i][j] X;}}}}public void dfs(char[][] board, int i, int j){if(i 0 || i board.length || j 0 || j board[0].length || board[i][j] X || board[i][j] A){return;}board[i][j] A;dfs(board, i - 1, j);dfs(board, i 1, j);dfs(board, i, j - 1);dfs(board, i, j 1);}
}
// bfs
class Solution {public void solve(char[][] board) {for(int i 0; i board.length; i){if(board[i][0] O){bfs(board, i, 0);}if(board[i][board[0].length - 1] O){bfs(board, i, board[0].length - 1);}}for(int j 1; j board[0].length - 1; j){if(board[0][j] O){bfs(board, 0, j);}if(board[board.length - 1][j] O){bfs(board, board.length - 1, j);}}for(int i 0; i board.length; i){for(int j 0; j board[0].length; j){if(board[i][j] A){board[i][j] O;}else if(board[i][j] O){board[i][j] X;}}}}public void bfs(char[][] board, int i, int j){Queueint[] queue new LinkedList();queue.offer(new int[]{i, j});while(!queue.isEmpty()){int[] cur queue.poll();i cur[0];j cur[1];if(i 0 i board.length j 0 j board[0].length board[i][j] O){board[i][j] A;queue.offer(new int[]{i - 1, j});queue.offer(new int[]{i 1, j});queue.offer(new int[]{i, j - 1});queue.offer(new int[]{i, j 1});}}}
}
