做网站如何对接支付,怎么做网站代拍,呼和浩特网站网站建设,滁州做网站力扣爆刷第145天之图论五连刷#xff08;dfs和bfs#xff09; 文章目录 力扣爆刷第145天之图论五连刷#xff08;dfs和bfs#xff09;总结一、797. 所有可能的路径二、200. 岛屿数量三、695. 岛屿的最大面积四、1020. 飞地的数量五、130. 被围绕的区域 总结
dfs是一条路走…力扣爆刷第145天之图论五连刷dfs和bfs 文章目录 力扣爆刷第145天之图论五连刷dfs和bfs总结一、797. 所有可能的路径二、200. 岛屿数量三、695. 岛屿的最大面积四、1020. 飞地的数量五、130. 被围绕的区域 总结
dfs是一条路走到底类似于树的遍历即一直递归直至终点。 bfs是一圈一圈的往外遍历类似于树的水平遍历一般使用队列来做。bfs适合来求两点之间的最短路径。
一、797. 所有可能的路径
题目链接https://leetcode.cn/problems/all-paths-from-source-to-target/description/ 思路本题求所有可能的路径从0到n-1节点的路径本题是有向无环图让我们搜索所有的路径本质上和遍历树没啥区别只不过是多叉树寻找路径自然是深度优先为了能在递归返回时再记录其他的路径自然要使用回溯那么本题就是dfs然后加上回溯本质上来说回溯也是深度优先。不过本题是有向无环图且定向路径不需要去重。
class Solution {ListListInteger result new ArrayList();ListInteger list new ArrayList();public ListListInteger allPathsSourceTarget(int[][] graph) {list.add(0);dfs(graph, 0);return result;}void dfs(int[][] graph, int start) {if(graph.length-1 start) {result.add(new ArrayList(list));return;}for(int i 0; i graph[start].length; i) {list.add(graph[start][i]);dfs(graph, graph[start][i]);list.remove(list.size()-1);}}
}二、200. 岛屿数量
题目链接https://leetcode.cn/problems/number-of-islands/description/ 思路dfs和bfs都可以这里使用dfs外部遍历只要是岛屿就计数并进行dfs在进行dfs的过程中只要是岛屿就设置为海洋然后向周围四个方向进行dfs这样一次递归返回即可标记一个岛。
class Solution {public int numIslands(char[][] grid) {int sum 0;for(int i 0; i grid.length; i) {for(int j 0; j grid[0].length; j) {if(grid[i][j] 1) {dfs(grid, i, j);sum;}}}return sum;}void dfs(char[][] grid, int x, int y) {if(x 0 || x grid.length || y 0 || y grid[0].length || grid[x][y] 0) return ;grid[x][y] 0;dfs(grid, x1, y);dfs(grid, x-1, y);dfs(grid, x, y1);dfs(grid, x, y-1);}}三、695. 岛屿的最大面积
题目链接https://leetcode.cn/problems/max-area-of-island/description/ 思路求岛屿的最大面积和上一题是类似上一题是求岛屿的数量本题只需要在每一次对一个岛屿进行dfs时进行累加遍历完再记录最大值清空记录值以此往复即可。
class Solution {int max 0, k 0;public int maxAreaOfIsland(int[][] grid) {for(int i 0; i grid.length; i) {for(int j 0; j grid[0].length; j) {if(grid[i][j] 1) {k 0;dfs(grid, i, j);max Math.max(max, k);}}}return max;}void dfs(int[][] grid, int x, int y) {if(x 0 || x grid.length || y 0 || y grid[0].length || grid[x][y] 0) return;k;grid[x][y] 0;dfs(grid, x-1, y);dfs(grid, x1, y);dfs(grid, x, y-1);dfs(grid, x, y1); }
}四、1020. 飞地的数量
题目链接https://leetcode.cn/problems/number-of-enclaves/description/ 思路求飞地的数量本题也是dfs看看只要掌握了dfs常见的图论的题目都可以做本题对飞地的顶用是不与边界接壤的土地本质上还是求所有岛屿的面积只不过在记录的过程中需要一个标志位记录该岛屿是否是飞地只有是飞地面积才会累加。
class Solution {boolean flag true;int count 0, k 0;public int numEnclaves(int[][] grid) {for(int i 0; i grid.length; i) {for(int j 0; j grid[0].length; j) {if(grid[i][j] 1) {k 0;flag true;dfs(grid, i, j);if(flag) count k; }}}return count;}void dfs(int[][] grid, int x, int y) {if(x 0 || x grid.length || y 0 || y grid[0].length || grid[x][y] 0) return;if(x 0 || x grid.length-1 || y 0 || y grid[0].length-1) flag false;k;grid[x][y] 0;dfs(grid, x-1, y);dfs(grid, x1, y);dfs(grid, x, y-1);dfs(grid, x, y1);}
}五、130. 被围绕的区域
题目链接https://leetcode.cn/problems/surrounded-regions/description/ 思路也是经典的海岛问题和上一题不一样的是让把节点相接壤的区域给保留下来只需要先沿着边界递归把与边界相接壤的岛屿先设置为一种标记然后全文遍历把不接壤的设置为海洋再把接壤的给还原回来。
class Solution {public void solve(char[][] board) {int m board.length, n board[0].length;for(int i 0; i m; i) {dfs(board, i, 0);dfs(board, i, n-1);}for(int i 0; i n; i) {dfs(board, 0, i);dfs(board, m-1, i);}for(int i 0; i m; i) {for(int j 0; j n; j) {if(board[i][j] O) board[i][j] X;if(board[i][j] A) board[i][j] O;}}}void dfs(char[][] board, int x, int y) {if(x 0 || x board.length || y 0 || y board[0].length || board[x][y] ! O) return;board[x][y] A;dfs(board, x-1, y);dfs(board, x1, y);dfs(board, x, y-1);dfs(board, x, y1);}
}
