门户网站安全建设wordpress 收费会员

当前位置： 首页 > news >正文

门户网站安全建设,wordpress 收费会员,成都小程序建设乚成都柚米,网络培训的功能主要有文章目录前言一、实现1.1 递归实现1.2 栈实现1.3 两者区别二、LeetCode 实战2.1 二叉树的前序遍历2.2 岛屿数量2.3 统计封闭岛屿的数目2.4 从先序遍历还原二叉树参考前言 深度优先搜索#xff08;Depth First Search#xff0c;DFS#xff09;是一种遍历或搜索树或图数据结… 文章目录前言一、实现1.1 递归实现1.2 栈实现1.3 两者区别二、LeetCode 实战2.1 二叉树的前序遍历2.2 岛屿数量2.3 统计封闭岛屿的数目2.4 从先序遍历还原二叉树参考前言 深度优先搜索Depth First SearchDFS是一种遍历或搜索树或图数据结构的算法。该算法从根节点开始在图的情况下选择一些任意的节点作为根节点并在回溯之前尽可能地沿着每个分支进行探索。需要额外的内存通常是一个堆栈来跟踪到目前为止沿着指定分支发现的节点这有助于回溯。 深度优先搜索算法的特点 从一个起始节点开始沿着一条路径不断访问邻接节点直到没有未访问的邻接节点为止然后回溯到上一个节点继续访问其他邻接节点。利用栈或递归来实现。可以产生目标图的相应拓扑排序表。 深度优先搜索算法的优点 简单易实现。占用空间少。可以找到从起始节点到任意可达节点的路径。 深度优先搜索算法的缺点 不一定能找到最短路径或最优解。可能会陷入死循环或无限递归。 深度优先搜索算法的应用场景 拓扑排序 课程安排、工程进度、依赖关系模拟游戏如象棋、迷宫等连通性检测如判断图中是否有环等旅行商问题如求解最短路径等括号匹配如检查表达式中的括号是否匹配等二叉树、线段树、红黑树、图等数据结构的遍历 在本文中我们将介绍深度优先搜索算法的基本原理和实现方法并通过一些例题来展示其应用。 一、实现 1.1 递归实现 从一个起始节点开始沿着一条路径不断访问邻接节点直到没有未访问的邻接节点为止然后回溯到上一个节点继续访问其他邻接节点直到所有节点都被访问过为止。 示例代码如下 public void dfs(int start) {visited[start] true; //将起始节点标记为已访问for (int i 0; i n; i) { //遍历邻接矩阵中start所在行if (matrix[start][i] 1 !visited[i]) { //如果存在边且未被访问过dfs(i); //递归调用dfs方法以该节点为新起点进行遍历}} }1.2 栈实现 从一个起始节点开始将其压入栈中然后重复以下步骤弹出栈顶元素并将其标记为已访问将该元素的所有未访问的邻接节点压入栈中。直到栈为空为止 示例代码如下 public void dfs(int start) {StackInteger stack new Stack(); //创建栈对象stack.push(start); //起始节点入栈SetInteger visited new HashSet(); //创建集合对象visited.add(start); //起始节点加入集合while (!stack.isEmpty()) { //只要栈不为空就继续循环int cur stack.peek(); //获取栈顶元素但不出栈boolean flag false; //设置标志位表示是否有未访问过的邻接节点for (int i 0; i n; i) { //遍历邻接矩阵中cur所在行if (matrix[cur][i] 1 !visited.contains(i)) { //如果存在边且未被访问过stack.push(i); //将该节点入栈visited.add(i); //将该节点加入集合System.out.print(i ); //打印该节点flag true; //修改标志位为true表示有未访问过的邻接节点break; //跳出循环以该节点为新起点进行遍历}}if (!flag) { //如果没有未访问过的邻接节点则说明已经到达最深处需要回溯上一层继续遍历其他分支路径。stack.pop(); //将栈顶元素出栈 }} }下面是一个dfs搜索的动图 1.3 两者区别 递归实现是利用系统栈来保存当前节点的状态当遇到死路时自动回溯到上一个节点继续搜索。而栈实现是利用自定义的栈来保存当前节点的状态当遇到死路时手动弹出栈顶元素回溯到上一个节点继续搜索。递归实现比较简洁易懂但是效率不高而且对于规模较大的图可能会导致栈溢出。而栈实现比较复杂一些但是效率更高而且可以避免栈溢出的问题。递归实现和栈实现都需要一个标志数组来记录哪些节点已经被访问过以防止重复访问或者陷入环路。 二、LeetCode 实战 2.1 二叉树的前序遍历

1. 二叉树的前序遍历 给你二叉树的根节点 root 返回它节点值的 前序 遍历。 ListInteger ans new ArrayList(); //定义一个整数列表用来存储前序遍历的结果 public ListInteger preorderTraversal(TreeNode root) {if (root ! null) { //如果当前节点不为空才进行以下操作ans.add(root.val); //把当前节点的值加入列表preorderTraversal(root.left); //递归地对左子树进行前序遍历preorderTraversal(root.right); //递归地对右子树进行前序遍历}return ans; //返回前序遍历的结果 }2.2 岛屿数量
2. 岛屿数量 给你一个由 1陆地和 0水组成的的二维网格请你计算网格中岛屿的数量。 岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外你可以假设该网格的四条边均被水包围。 // 定义一个二维数组pos表示四个方向 int[][] pos { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; // 定义一个变量ans表示岛屿的数量 int ans 0;// 定义一个方法numIslands接受一个二维字符数组grid作为参数返回岛屿的数量 public int numIslands(char[][] grid) {// 获取grid的行数和列数int m grid.length, n grid[0].length;// 定义一个二维布尔数组visited表示每个位置是否被访问过boolean[][] visited new boolean[m][n];// 遍历grid中的每个位置for (int i 0; i m; i) {for (int j 0; j n; j) {// 如果当前位置是1且没有被访问过则从该位置开始深度优先搜索并将ans加一if (grid[i][j] 1 !visited[i][j]) {dfs(grid, visited, i, j);ans;}}}// 返回ans作为结果return ans; }// 定义一个方法dfs接受一个二维字符数组grid、一个二维布尔数组visited、两个整数i和j作为参数无返回值 public void dfs(char[][] grid, boolean[][] visited, int i, int j) {// 如果i或j越界或者当前位置是0或者已经被访问过则直接返回if (i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0|| visited[i][j]) {return;}// 将当前位置标记为已访问visited[i][j] true;// 遍历四个方向并递归调用dfs方法for (int[] p : pos) {dfs(grid, visited, i p[0], j p[1]);}}2.3 统计封闭岛屿的数目
3. 统计封闭岛屿的数目 二维矩阵 grid 由 0 土地和 1 水组成。岛是由最大的4个方向连通的 0 组成的群封闭岛是一个 完全 由1包围左、上、右、下的岛。 请返回 封闭岛屿 的数目。 // 定义一个二维数组pos来存储上下左右四个方向的偏移量 int[][] pos { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; // 定义一个变量ans来记录封闭岛屿的个数 int ans 0;public int closedIsland(int[][] grid) {// 判断矩阵是否为空如果为空直接返回0if (grid null || grid.length 0 || grid[0].length 0) {return 0;}// 获取矩阵的行数和列数int m grid.length, n grid[0].length;// 遍历矩阵中的每一个元素for (int i 0; i m; i) {for (int j 0; j n; j) {// 如果当前元素是岛屿0则调用dfs函数来检查它是否被水域1完全包围if (grid[i][j] 0 dfs(grid, i, j)) {// 如果dfs函数返回true说明当前岛屿是封闭的ans加一ans;}}}// 返回ans作为最终答案return ans; } public boolean dfs(int [][] grid, int i, int j) {// 如果当前坐标超出了矩阵的边界说明当前岛屿不是封闭的返回falseif (i 0 || i grid.length || j 0 || j grid[0].length) {return false;}// 如果当前元素是水域1说明没有遇到边界返回trueif (grid[i][j] 1) {return true;}// 将当前元素标记为水域1避免重复访问grid[i][j] 1;// 使用一个for循环来遍历上下左右四个方向并将结果进行逻辑与运算boolean res true;for (int [] p: pos) {res dfs(grid, i p[0], j p[1]);}// 返回res作为dfs函数的结果return res; }2.4 从先序遍历还原二叉树
4. 从先序遍历还原二叉树 我们从二叉树的根节点 root 开始进行深度优先搜索。 在遍历中的每个节点处我们输出 D 条短划线其中 D 是该节点的深度然后输出该节点的值。如果节点的深度为 D则其直接子节点的深度为 D 1。根节点的深度为 0。 如果节点只有一个子节点那么保证该子节点为左子节点。 给出遍历输出 S还原树并返回其根节点 root。 int index 0; // 定义全局变量indexpublic TreeNode recoverFromPreorder(String traversal) {int[] deep Arrays.stream(traversal.split([0-9]{1,10})).mapToInt(String::length).toArray(); // 将输入字符串按照数字分割成数组deepint[] number Arrays.stream(traversal.split(-{1,100})).mapToInt(Integer::parseInt).toArray(); // 将输入字符串按照连字符分割成数组numberif (deep.length 0) deep new int[]{0}; // 如果deep为空则赋值为[0]return dfs(deep, number); // 调用dfs函数并返回结果 }public TreeNode dfs(int [] deep, int [] number) {TreeNode treeNode new TreeNode(number[index]); // 创建新的TreeNode对象并赋值int curHeight deep[index]; // 获取当前节点的深度if (index 1 deep.length curHeight deep[index 1] - 1) { // 判断是否有左子节点index; // 将index加1treeNode.left dfs(deep, number); // 递归调用dfs并赋值给左子节点}if (index 1 deep.length curHeight deep[index 1] - 1) { // 判断是否有右子节点index; // 将index加1treeNode.right dfs(deep, number); // 递归调用dfs并赋值给右子节点}return treeNode; // 返回当前节点 }参考 https://en.wikipedia.org/wiki/Depth-first_searchhttps://zh.wikipedia.org/wiki/深度优先搜索深度优先搜索 —— 新手上路的一道坎