如何优化360网站排名，加强二级教育网站的招生效果？

如何做360网站的排名,加强二级网站建设 招生,外贸网上推广,网站的配色技巧最近在刷力扣时遇见的问题#xff0c;自己总结加上看了力扣大佬的知识总结写下本篇文章#xff0c;我们所熟悉的 DFS#xff08;深度优先搜索#xff09;问题通常是在树或者图结构上进行的。而我们今天要讨论的 DFS 问题#xff0c;是在一种「网格」结构中进行的。岛屿问题… 最近在刷力扣时遇见的问题自己总结加上看了力扣大佬的知识总结写下本篇文章我们所熟悉的 DFS深度优先搜索问题通常是在树或者图结构上进行的。而我们今天要讨论的 DFS 问题是在一种「网格」结构中进行的。岛屿问题是这类网格 DFS 问题的典型代表。网格结构遍历起来要比二叉树复杂一些如果没有掌握一定的方法DFS 代码容易写得冗长繁杂。 目录 一、网格类问题的DFS遍历方法 1.1网格问题基本概念  1.2 DFS的基本结构 1.3 如何避免重复遍历 二、岛屿经典例题 2.1 岛屿数量 2.2 岛屿的周长 2.3 单词搜索 一、网格类问题的DFS遍历方法 1.1网格问题基本概念 网格问题是由 m×n 个小方格组成一个网格每个小方格与其上下左右四个方格认为是相邻的要在这样的网格上进行某种搜索。岛屿问题是一类典型的网格问题。每个格子中的数字可能是 0 或者 1。 数字为1的格子连接起来就形成一个岛屿。 1.2 DFS的基本结构 首先我们要确定访问的下一个节点以及停止的边界那么首先网格结构中的每个格子可以向四周延伸分别为上下左右对于格子(r,c)来说对应的四个坐标分别为(r1,c)、(r-1,c)、(r,c-1)、(r,c1)。 其次超出格子的边界是什么?是grid[r][c]出现下标越界异常的格子也就是那些超出范围的格子。 这样我们就得到了网格DFS遍历的框架代码 public void infect(char[][] grid,int i ,int j){ //超出范围if (i 0 || i grid.length || j 0 || j grid[0].length){return;} //访问上下左右infect(grid,i1,j);infect(grid,i-1,j);infect(grid,i,j1);infect(grid,i,j-1); } 1.3 如何避免重复遍历 网格结构的 DFS 与二叉树的 DFS 最大的不同之处在于遍历中可能遇到遍历过的结点。这是因为网格结构本质上是一个「图」我们可以把每个格子看成图中的结点每个结点有向上下左右的四条边。在图中遍历时自然可能遇到重复遍历结点。 如何避免这样的重复遍历呢答案是将已经遍历过的格子的值修改一下每次走过一个格子就修改格子的值。以岛屿问题为例我们需要在所有值为 1 的陆地格子上做 DFS 遍历。每走过一个陆地格子就把格子的值改为 2这样当我们遇到 2 的时候就知道这是遍历过的格子了。 public void infect(char[][] grid,int i ,int j){if (i 0 || i grid.length || j 0 || j grid[0].length ){return;}grid[i][j] 2;infect(grid,i1,j);infect(grid,i-1,j);infect(grid,i,j1);infect(grid,i,j-1);} 二、岛屿经典例题 2.1 岛屿数量 岛屿类问题的通用解法、DFS 遍历框架 - 岛屿数量 - 力扣LeetCode 0 —— 海洋格子1 —— 陆地格子未遍历过2 —— 陆地格子已遍历过class Solution {public int numIslands(char[][] grid) {int islandNum 0;for (int i 0; i grid.length; i) {for (int j 0; j grid[0].length; j) {if (grid[i][j] 1){infect(grid,i,j);islandNum;}}}return islandNum;}public void infect(char[][] grid,int i ,int j){if (i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] ! 1){return;}grid[i][j] 2;infect(grid,i1,j);infect(grid,i-1,j);infect(grid,i,j1);infect(grid,i,j-1);} } 2.2 岛屿的周长 463. 岛屿的周长 - 力扣LeetCode 给你一个由 1陆地和 0水组成的的二维网格请你计算网格中岛屿的数量。 网格中的格子 水平和垂直 方向相连对角线方向不相连。整个网格被水完全包围但其中恰好有一个岛屿或者说一个或多个表示陆地的格子相连组成的岛屿。 我们可以将岛屿的周长中的边分为两类如下图所示。黄色的边是与网格边界相邻的周长而蓝色的边是与海洋格子相邻的周长。 当我们的 dfs 函数因为「坐标 (r, c) 超出网格范围」返回的时候实际上就经过了一条黄色的边而当函数因为「当前格子是海洋格子」返回的时候实际上就经过了一条蓝色的边。 本题我们可以再次嵌套DFS的框架但是要增加几处地方实际上岛屿的周长是计算岛屿全部的「边缘」而这些边缘就是我们在 DFS 遍历中dfs 函数返回的位置。 class Solution {public int islandPerimeter(int[][] grid) {for (int r 0; r grid.length; r) {for (int c 0; c grid[0].length; c) {if (grid[r][c] 1){return dfs(grid,r,c);}}}return 0;}public int dfs(int[][] grid,int r,int c){if (r 0 || r grid.length ||c 0 || c grid[0].length ){return 1;}if (grid[r][c] 0){return 1;}if (grid[r][c] ! 1){return 0;}grid[r][c] 2;return dfs(grid,r-1,c)dfs(grid,r1,c)dfs(grid,r,c-1)dfs(grid,r,c1);} }2.3 单词搜索 79. 单词搜索 - 力扣LeetCode 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中返回 true 否则返回 false 。 本题在使用上面的DFS框架时要加上回溯因为当搜索一次时会更改当前的格子的值 如果我在DFS的过程中不改矩阵的状态那我就会出现重复搜索的情况啊这可不行因此矩阵是必须得改的。那就只剩下一个办法了每次DFS的过程中修改矩阵DFS完了再把矩阵给改回去呗这就是回溯 那么什么是剪枝呢所谓剪枝就是我在dfs的时候如果已经找到一个正确的路径了换句话说已经得到结果了其实就没必要继续DFS了直接返回结果即可。这就是剪枝。 给一下官方的说法剪枝就是减小树的规模尽早排除搜索树中不必要的分支的一种手段。 class Solution {private boolean find;public boolean exist(char[][] board, String word) {if(board null){return false;}int m board.length,n board[0].length;boolean[][] visited new boolean[m][n];find false;for(int i 0;i m;i){for(int j 0 ;j n;j){backtracking(i, j, board, word, visited, 0);}}return find;}/*** i,j,board棋盘格及当前元素的坐标* word: 要搜索的目标单词* visited记录当前格子是否已被访问过* pos: 记录目标单词的字符索引只有棋盘格字符和pos指向的字符一致时才有机会继续搜索接下来的字符如果pos已经过了目标单词的尾部了那么便说明找到目标单词了*/public void backtracking(int i, int j, char[][] board, String word, boolean[][] visited, int pos){// 超出边界、已经访问过、已找到目标单词、棋盘格中当前字符已经和目标字符不一致了if(i 0 || i board.length || j 0 || jboard[0].length || visited[i][j] || find || board[i][j] ! word.charAt(pos)){return;}if(pos word.length()-1){find true;return;}visited[i][j] true;// 修改当前节点状态backtracking(i1, j, board, word, visited, pos1); // 遍历子节点backtracking(i-1, j, board, word, visited, pos1);backtracking(i, j1, board, word, visited, pos1);backtracking(i, j-1, board, word, visited, pos1);visited[i][j] false; // 撤销修改} } 如果对你有帮助麻烦双击三连一下谢谢啦