中南建设网官方网站,用一个口罩做一把枪,东莞常平美食,网站首页被降权怎么做回溯算法——DFSDFS介绍(Depth First Search)DFS经典题目1. 员工的重要性2. 图像渲染3.被围绕的区域4.岛屿数量5. 电话号码的字母组合6.数字组合7. 活字印刷8. N皇后DFS介绍(Depth First Search)
回溯法#xff08;back tracking#xff09;#xff08;探索与回溯法#x…
回溯算法——DFSDFS介绍(Depth First Search)DFS经典题目1. 员工的重要性2. 图像渲染3.被围绕的区域4.岛屿数量5. 电话号码的字母组合6.数字组合7. 活字印刷8. N皇后DFS介绍(Depth First Search)
回溯法back tracking探索与回溯法回溯算法实际上一个类似枚举的搜索尝试过程主要是在搜索尝试过程中寻找问题的解当发现已不满足求解条件时就“回溯”返回尝试别的路径。回溯法是一种选优搜索法按选优条件向前搜索以达到目标。但当探索到某一步时发现原先选择并不优或达不到目标就退回一步重新选择这种走不通就退回再走的技术为回溯法而满足回溯条件的某个状态的点称为“回溯点”。也可以称为剪枝点所谓的剪枝指的是把不会找到目标或者不必要的路径裁剪掉。DFS算法就是深度优先算法在数据结构的学习中二叉树的前序遍历就是属于深度优先算法。
深度优先搜索其实就是一条路走到黑。我们来看一道很经典的DFS题目让我们来了解深度优先搜索。
✨问题描述
假如有编号为1~ 3的3张扑克牌和编号为1~3的3个盒子现在需要将3张牌分别放到3个盒子中去且每个盒子只能放 一张牌一共有多少种不同的放法
✨ 思路分析 上面这张图画出了回溯过程的前半部分接下来按着深度优先搜索的方式接着进行回溯我们可以得到剩下的三种情况 我们进行上述的深度优先搜索的时候我们在一个盒子中放扑克牌是从1 – 3号扑克牌依次进行放入的这样我们可以用for循环搞定。但是我们如何确定该位置要放的扑克牌是否在前面已经被放过了呢我们可以使用一个标记数组 int[] book 来记录当前扑克牌在前面是否被放入了。
✨ 代码实现 public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();//盒子和牌的个数int[] book new int[n 1];int[] box new int[n 1];Dfs(1,book,box,n);}private static void Dfs(int idx, int[] book, int[] box, int n) {if (idx n 1){//此时已经完成了一次深度优先搜索for (int i 1; i n; i) {System.out.print(box[i] );}System.out.println();return;}for (int i 1; i n; i) {//深度优先搜索去放置牌if(book[i] 0){box[idx] i;//idx个盒子放第i个牌book[i] 1;//代表第i个牌已经使用了Dfs(idx 1, book, box, n);//处理下一个盒子book[i] 0;//第i张牌重新拿到手里}}}
DFS经典题目
1. 员工的重要性
原题链接
✨问题描述
给定一个保存员工信息的数据结构它包含了员工 唯一的 id 重要度 和 直系下属的 id 。 比如员工 1 是员工 2 的领导员工 2 是员工 3 的领导。他们相应的重要度为 15 , 10 , 5 。那么员工 1 的数据结构是 [1, 15, [2]] 员工 2的 数据结构是 [2, 10, [3]] 员工 3 的数据结构是 [3, 5, []] 。注意虽然员工 3 也是员工 1 的一个下属但是由于 并不是直系 下属因此没有体现在员工 1 的数据结构中。 现在输入一个公司的所有员工信息以及单个员工 id 返回这个员工和他所有下属的重要度之和。
✨输入案例
输入[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1 输出11 解释 员工 1 自身的重要度是 5 他有两个直系下属 2 和 3 而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5 3 3 11 。
✨题目分析
该问题就类似于二叉树的前序遍历。从单个员工的重要度开始计算依次遍历员工的下属下属有员工再次搜索下属。直到没有下属员工再依次回退查看有没有其他的子员工。
✨ 解题代码 public int getImportance(ListEmployee employees, int id) {MapInteger,Employee empMap new HashMap();//用哈希表存储数据查找会更方便更快速。for (Employee employee: employees) {empMap.put(employee.id,employee);}return DFS(empMap,id);}private int DFS(MapInteger, Employee empMap, int id) {int sum empMap.get(id).importance;//加上该员工的重要度for (int curId:empMap.get(id).subordinates) {//该员工有下属就进行for-each循环DFS没有的话就不进去循环sum DFS(empMap,curId);}return sum;}2. 图像渲染
原题链接
✨问题描述
有一幅以 m x n 的二维整数数组表示的图画 image 其中 image[i][j] 表示该图画的像素值大小。 你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。 为了完成 上色工作 从初始像素开始记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点……重复该过程。将所有有记录的像素点的颜色值改为 newColor 。 最后返回 经过上色渲染后的图像 。
✨题目样例
案例1 输入: image [[1,1,1],[1,1,0],[1,0,1]]sr 1, sc 1, newColor 2 输出: [[2,2,2],[2,2,0],[2,0,1]] 解析: 在图像的正中间(坐标(sr,sc)(1,1)),在路径上所有符合条件的像素点的颜色都被更改成2。 注意右下角的像素没有更改为2因为它不是在上下左右四个方向上与初始点相连的像素点。 案例2 输入: image [[0,0,0],[0,0,0]], sr 0, sc 0, newColor 2 输出: [[2,2,2],[2,2,2]] ✨ 题目分析
这个题目用DFS算法来解决。把初始四围与其颜色相同的位置进行渲染渲染了一个位置就找其周围与其颜色相同的位置进行渲染。同时还需要判断四周的位置是否越界。如果渲染颜色和初始位置的颜色不同的话我们渲染时候仅仅需要判断是否为原始位置的颜色相同渲染后的位置和未被渲染的位置能够清楚的区分但是如果初始位置的颜色和渲染染色相同就会区分不了该位置是渲染过的还是未被渲染的和初始位置原色相同的。为了解决这个问题我们就引入一个标记数组 int[][] book 来标记该位置是否被渲染过了。
✨ 解题代码 int[][] nextP {{1,0},{-1,0},{0,-1},{0,1}};//偏移数组通过原位置找到相邻的四个位置public int[][] floodFill(int[][] image, int sr, int sc, int color) {int oldColor image[sr][sc];//记录要修改坐标的旧颜色int row image.length;int col image[0].length;int[][] book new int[row][col];//创建一个标记数组DFS(image,book,sr,sc,oldColor,color,row,col);//深度优先搜索寻找是否有相同颜色的位置return image;}private void DFS(int[][] image, int[][] book, int sr, int sc, int oldColor, int color,int row,int col) {image[sr][sc] color;//修改当前位置的颜色book[sr][sc] 1;//标记当前位置已经被修改过了for (int i 0; i 4; i) {//搜索上下左右四个位置的颜色是否符合原颜色int newX sr nextP[i][0];int newY sc nextP[i][1];if (newX 0 || newX row|| newY 0 || newY col) {//判断新坐标是否越界continue;}//判断当前位置是否需要进行图像渲染if (image[newX][newY] oldColor book[newX][newY] 0){//新的位置的处理DFS(image,book,newX,newY,oldColor,color,row,col);}}}3.被围绕的区域
原题链接
✨问题描述
给你一个 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”]] ✨ 题目分析 把整个区域扩大一下变成上图这种。上图中红圈里的就是被包围的区域被包围的区域比较不容易找到但是未被包围的区域就比较容易的找到了。我们可以用深度优先搜索的方式进行找到没有被包围的区域间接找到被包围的区域。
✨ 解题代码 int[][] nextP {{1,0},{-1,0},{0,1},{0,-1}};//方向数组下一步从哪个方向搜索 下 上 右 左public void solve(char[][] board) {int row board.length;int col board[0].length;//用逆向思维的方式求未被包围的区域间接求出被包围的区域for (int i 0; i row; i) {//寻找左列边界的区域中‘O’的位置if (board[i][0] O){DFS(board,i,0,row,col);}if (board[i][col - 1] O){//寻找右列边界的区域中‘O’的位置DFS(board,i,col - 1,row,col);}}for (int j 0; j col; j) {if (board[0][j] O){//判断上边界是否有‘O’DFS(board,0,j,row,col);}if (board[row - 1][j] O){//判断下边界是否有‘O’DFS(board,row - 1,j,row,col);}}for (int i 0; i row; i) {for (int j 0; j col; j) {if (board[i][j] O){board[i][j] X;}if (board[i][j] *){board[i][j] O;}}}}private void DFS(char[][] board, int x, int y, int row, int col) {board[x][y] *;//代表该‘O’已经被搜索过了for (int i 0; i 4; i) {int newX x nextP[i][0];int newY y nextP[i][1];if (newX 0 || newX row||newY 0 || newY col){//判断探索位置是否越界continue;}if (board[newX][newY] O){//判断该位置是否需要进行探索DFS(board,newX,newY,row,col);}}}
4.岛屿数量
原题链接
✨ 题目描述
给你一个由 ‘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 ✨ 题目分析
这个问题和第二题的思路有很多类似的地方。都是进行一个深度优先搜索但是第二题给出了搜索的起始位置。这个题目搜索的起始位置我们可以对整个数组进行遍历。我们可以对搜索过的陆地位置进行标记因为此问题我们仅仅只有‘0’和‘1’两种情况我们可以对grid数组本身进行进行字符的改变来表示他是一个已经被搜索过的陆地了这个字符我们可以换成一个不同于‘0’和‘1’的比如‘*’
✨ 解题代码 int[][] nextP {{1,0},{-1,0},{0,1},{0,-1}};//方向数组下一步从哪个方向搜索 下 上 右 左public int numIslands(char[][] grid) {int row grid.length;int col grid[0].length;int count 0;for (int i 0; i row; i) {for (int j 0; j col; j) {if (grid[i][j] 1){DFS(grid,i,j,row,col);count;}}}return count;}private void DFS(char[][] grid,int posX, int poxY ,int row, int col) {grid[posX][poxY] *;//对已经搜索过的陆地进行标记以防重复搜索造成死递归。for (int i 0; i 4; i) {int newX posX nextP[i][0];int newY poxY nextP[i][1];if (newX 0 || newX row|| newY 0 || newY col) {//判断是否是越界了continue;}if (grid[newX][newY] 1){//是未被搜索的陆地就进行下一步搜索DFS(grid, newX, newY, row, col);}}}5. 电话号码的字母组合
原题链接
✨ 题目描述
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
✨ 题目案例
案例1 输入digits “23” 输出[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”] 案例2 输入digits “” 输出[] 案例3 输入digits “2” 输出[“a”,“b”,“c”] ✨ 题目分析
结合案例可以看出这个问题得到的字母组合和digits字符串的长度相同。当digits长度为0的时候得到的结果是没有任何元素的一个集合。我们可以建立一个联系用电话按键数字对应字符串在深度优先搜索的时候用于查找我们数字对应的字符串我们一听到建立关系用于查找我们第一反应是建立hashMap但是在java中的hashMap一下定义那么多关系书写时比较麻烦的我们可以用字符串数组来代替hashMap来实现建立这个关系用数组的下标(数字)来对应数组内容(字符串)。 我们这个问题在运用深度优先搜索对于前几个题不同的是不是每个位置放置的内容可以相互交换而是每个位置的数字对应的字符串依次放在对应位置。
✨ 题目代码 public ListString letterCombinations(String digits) {ListString list new ArrayList();String curStr ;int len digits.length();//所需获得字符串的长度DFS(digits,list,curStr,0,len);return list;}String[] strings {,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};private void DFS(String digits, ListString list, String curStr, int digitIdx,int len) {if (len digitIdx){if (len ! 0){list.add(curStr);}return;}//进行深度优先搜索,int num Integer.parseInt(digits.charAt(digitIdx) );//获取当钱位置的数字字符for (char ch: strings[num].toCharArray()) {DFS(digits,list,curStr ch,digitIdx 1,len);}}6.数字组合
原题链接
✨ 题目描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。 对于给定的输入保证和为 target 的不同组合数少于 150 个。
✨ 题目案例
案例1 输入candidates [2,3,6,7], target 7 输出[[2,2,3],[7]] 解释 2 和 3 可以形成一组候选2 2 3 7 。注意 2 可以使用多次。 7 也是一个候选 7 7 。 仅有这两种组合。 案例2 输入: candidates [2,3,5], target 8 输出: [[2,2,2,2],[2,3,3],[3,5]] 案例3 输入: candidates [2], target 1 输出: [] ✨ 题目解析
我们这个题目也是用DFS进行解决。我们对一个数字进行递归直到这个组合的数字和大于等于目标数字的时候我们进行终止继续向下搜索我们需要进行回溯到上一个步骤试试其他的数字怎么样。 下面就是案例1的DFS过程 这个问题为了避免出现一个组合重复出现的情况我们可以在DSF的时候循环遍历从该数字对应字符串的位置往后进行搜索。
✨ 解题代码
DFS求解需要注意的是allRet.add(new ArrayList(curRet)); 其中两个对象的类型都是List所以我们得转化为 ArrayList()这种具体类 public ListListInteger combinationSum(int[] candidates, int target) {ListListInteger allRet new ArrayList(new ArrayList());ListInteger curRet new ArrayList();int curSum 0;//搜索当前情况下的数字和int prev 0;//当前你所需要的DFS时加和的下标DFS(candidates,target,allRet,curRet,curSum,prev);return allRet;}private void DFS(int[] candidates, int target, ListListInteger allRet, ListInteger curRet, int curSum, int prev) {if (curSum target){if (curSum target){//保存当前的解集allRet.add(new ArrayList(curRet));}return;}//累加的起始位置为上一项的位置for (int i prev; i candidates.length; i) {//累加当前项curRet.add(candidates[i]);DFS(candidates,target,allRet,curRet,curSum candidates[i],i);//回溯curRet.remove(curRet.size() - 1);}}7. 活字印刷
原题链接
✨ 题目描述 你有一套活字字模 tiles其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。 注意本题中每个活字字模只能使用一次。
✨ 题目案例
案例1 输入“AAB” 输出8 解释可能的序列为 “A”, “B”, “AA”, “AB”, “BA”, “AAB”, “ABA”, “BAA”。 案例2 输入“AAABBC” 输出188 案例3 输入“V” 输出1 提示
1 tiles.length 7tiles 由大写英文字母组成
✨ 题目分析
该题目一样是用DFS来进行解题。但是改题目不一样的地方是每个活字字模只能使用一次也就是每个位置的字符只能用一次我们为了避免出现一个位置的字符进行多次出现我们可以创建一个标记数组来标记是否该位置的字符已经在搜索过程中被使用到了。
✨ 解题代码 public int numTilePossibilities(String tiles) {SetString set new HashSet();String curStr ;int[] book new int[tiles.length()];//标记字符串中的字符是否已经搜索过了。DFS(tiles,set,curStr,book);return set.size();}private void DFS(String tiles, SetString set, String curStr, int[] book) {if (curStr.length() ! 0){set.add(curStr);}if (curStr.length() tiles.length()){return;}for (int i 0; i tiles.length(); i) {if (book[i] 0){book[i] 1;//进行深度优先搜索DFS(tiles,set,curStr tiles.charAt(i),book);//进行回溯book[i] 0;}}}8. N皇后
✨ 题目描述
按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。 给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
✨ 题目案例
案例1 输入n 4输出[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]] 解释如上图所示4 皇后问题存在两个不同的解法。 案例2 输入n 1 输出[[“Q”]] ✨ 题目分析
我们就以案例1来进行DFS分析如下图 改图中展示 了找到其中一种n皇后的摆法其他摆法也是按照这种思路进行DFS和回溯。 我们现在最主要的是如何进行判断该位置是否是违规的位置。我们从横纵方向斜主对角线的坐标进行了以下分析
横x坐标相同 纵y坐标相同 正对角线newX - newY x - y(坐标差相同) 斜对角线newX newY x y(坐标和相同)
我们就可以针对已经摆放好的皇后来进行判断该位置是否违法不违法就可以摆放新的皇后摆放皇后的数量等于n就是一种摆放方式。
✨ 解题代码
class pair{public int x;public int y;public pair(int x, int y) {this.x x;this.y y;}
}
class Solution {public ListListString solveNQueens(int n) {ListListpair allRet new ArrayList();Listpair curRet new ArrayList();DFS(allRet,curRet,0,n);//System.out.println(allRet.toString());return transResult(allRet,n);}void DFS(ListListpair allRet,Listpair curRet,int curRow,int n){//如果每一行都没有冲突,则是一种可行方案if (curRow n){allRet.add(new ArrayList(curRet));return;}//确定当前行的每一个位置是否和已经确定的位置有冲突for (int i 0; i n; i) {if(isValidPos(curRet,curRow,i)){curRet.add(new pair(curRow,i));//把当前位置存放到当前情况中//处理下一行DFS(allRet,curRet,curRow 1,n);//回溯curRet.remove(curRet.size() - 1);//尾删}}}private boolean isValidPos(Listpair curRet, int row, int col) {for (pair pos: curRet) {if (pos.y col || pos.x pos.y row col|| pos.x - pos.y row - col){return false;}}return true;}private ListListString transResult(ListListpair allRet, int n) {ListListString allMet new ArrayList();for (Listpair curRet : allRet) {ListString curMat new ArrayList();for (pair pos: curRet) {StringBuilder str new StringBuilder();for (int i 0; i n; i) {str.append(.);}str.setCharAt(pos.y,Q);curMat.add(str.toString());}allMet.add(curMat);}return allMet;}}
