回溯算法之深度优先搜索

喜欢ヅ旅行 2024-03-16 12:32 56阅读 0赞

**目录**

放牌

员工的重要性

图像渲染

岛屿的周长

被围绕的区域

岛屿的数量

岛屿的最大面积

电话号码的字母组合

二进制手表

组合总和

活字印刷

N皇后

--------------------

深度优先搜索（Depth First Search）------ 一条道走到黑

## 放牌 ##

假如有编号为1~3的3张扑克牌和编号为1~3的3个盒子，现在需要将3张牌分别放到3个盒子中去，且每个盒子只能放一张牌，一共有多少种不同的放法。

步骤:

1.边界,如果遍历到了最后一个,输出遍历结果

2.遍历每一个牌

1.如果没有使用过,放入牌,盒子标记为1

2.进入下一个遍历

3.回溯,取出最后一个放入的牌

public static void Dfs(int index, int n, int[] boxs, int[] book){
        if(index==n+1){//边界:最后一个-->此时牌都放入了,直接输出结果
            //输出这一次的遍历结果
            for (int i = 1; i <=n ; i++) {
                System.out.print(boxs[i]+" ");
            }
            //一次结果输出后,回车
                System.out.println();
                return;
    
        }
        for(int i=1;i<=n;i++){
            //判断当前牌是否用过
            if(book[i]==0){
                //没有使用过,放入牌,盒子标记为1
                boxs[index]=i;
                book[i]=1;//i号牌已经使用
                //处理下一个盒子
                Dfs(index+1,n,boxs,book);
                //从下一个盒子回退到当前盒子,取出当前盒子的牌
                book[i]=0;
            }
        }
    }
    
    public static void main(String[] args) {
        int n;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();//盒子和牌个数
        int[] boxs = new int[n + 1];//盒子
        int[] books = new int[n + 1];//牌
        Dfs(1, n, boxs, books);
    }

## 员工的重要性 ##

![3347423c74d044469c30e4a1dd7db712.png][]

class Solution {
        public int DFS(Map<Integer,Employee> info, int id){
            //当前员工的import和他所有下属的import
            Employee curE=info.get(id);//得到id
            int sum=curE.importance;//通过id,得到import和
            for (int subId: curE.subordinates) {//遍历下属,得到总和
                sum+=DFS(info,subId);
            }
            return sum;
        }
        public int getImportance(List<Employee> employees, int id) {
            if(employees.isEmpty()){
                return 0;
            }
            Map<Integer,Employee> info=new HashMap<>();
            //信息放入info中
            for(Employee e:employees){
                info.put(e.id,e);//从list中取出list中的元素,放入info中
            }
            //遍历总和
            return DFS(info,id);
    
        }
    }

## 图像渲染 ##

![045a47b358bb47f5b7b9706e6192ff19.png][]

步骤:

floodFill

1.得到矩阵的长宽,指定位置原本的颜色

2.创建数组book,判断该位置是否遍历过

3.进入dfs

4.输出结果image

dfs

1.把当前位置颜色改变,标记为遍历过

2.遍历四个方向

3.得到新的位置

4.判断位置是否合法

5.判断是否和原颜色相同,是否标记过

5.满足要求,进行递归

class Solution {
        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,sr,sc,book,row,col,oldcolor,color);
            return image;
        }
        int[][] next={
       {1,0},{-1,0},{0,1},{0,-1}};
        public void dfs(int[][] image,int curx,int cury,int[][] book,int row,int col,int oldcolor,int color){
            image[curx][cury]=color;
            book[curx][cury]=1;
            for(int i=0;i<4;i++){
                int newx=curx+next[i][0];
                int newy=cury+next[i][1];
    
                if(newx>=row || newx<0 || newy>=col || newy<0){
                    continue;
                }
                if(image[newx][newy]==oldcolor && book[newx][newy]==0){
                    dfs(image,newx,newy,book,row,col,oldcolor,color);
                }
            }
        }
    
       
    }

## 岛屿的周长 ##

![8251a254aa4845e088a0fb5a07e5eca1.png][]

遍历,判断是不是陆地,如果是进入dfs

*  判断位置是否合法
 *  判断是否是水域,返回1
 *  判断不是陆地或标记过,返回0
 *  进入四个方向遍历

class Solution {
         public int islandPerimeter(int[][] grid) {
             for(int i=0;i<grid.length;i++){
                 for(int j=0;j<grid[0].length;j++){
                     if(grid[i][j]==1){
                         return dfs(grid,i,j);
                     }
                 }
             }
             return 0;
        }
        public int dfs(int[][] grid,int i,int j){
            //边界+1
            if(i<0 || i>=grid.length || j<0 || j>=grid[0].length){
                return 1;
            }
            //水域+1
            if(grid[i][j]==0){
                return 1;
            }
            //遍历过 在内部,周长不增加
            if(grid[i][j]!=1){
                return 0;
            }
            //遍历过,防止再次遍历
            grid[i][j]=2;
            return dfs(grid,i-1,j)+dfs(grid,i+1,j)+dfs(grid,i,j+1)+dfs(grid,i,j-1);
        }
    }

## 被围绕的区域 ##

![a47e49e2d2fd40b1972e231eba897cb4.png][]

从四个边遍历,把边上的O变为A,把剩下的O(此时的O都是被包围的)变为X,把A变为O

步骤:

*  solve
    
     *  找到第一行,第一列,最后一行,最后一列,进入dfs,直到不为O
 *  dfs
    
     *  标记当前位置
     *  遍历四个方向
     *  得到新的坐标\]
     *  判断坐标是否合法
     *  如果是O,并且没有标记过,进入下一个

class Solution {
       
        public void solve(char[][] board) {
            if(board==null){
                return ;
            }
         int row=board.length;
         int col=board[0].length;
         int[][] book=new int[row][col];
         for(int i=0;i<row;i++){
             if(book[i][0]==0 && board[i][0]=='O'){
                 dfs(board,i,0,row,col,book);
             }
    
             if(book[i][col-1]==0 && board[i][col-1]=='O'){
                 dfs(board,i,col-1,row,col,book);
             }
         }
    
         for(int i=0;i<col;i++){
             if(book[0][i]==0 && board[0][i]=='O'){
                 dfs(board,0,i,row,col,book);
             }
             if(book[row-1][i]==0  && board[row-1][i]=='O'){
                 dfs(board,row-1,i,row,col,book);
             }
         }
         for(int i=0;i<row;i++){
             for(int j=0;j<col;j++){
                 if(board[i][j]=='O'){
                     board[i][j]='X';
                 }else if(board[i][j]=='A'){
                     board[i][j]='O';
                 }
             }
         }
        }
        int[][] next={
       {1,0},{-1,0},{0,1},{0,-1}};
        public void dfs(char[][] board,int x,int y,int row,int col,int[][] book){
            book[x][y]=1;
            board[x][y]='A';
            for(int i=0;i<4;i++){
                int nx=x+next[i][0];
                int ny=y+next[i][1];
    
                if(nx<0 || nx>=row || ny<0 || ny>=col){
                    continue;
                }
    
                if(board[nx][ny]=='O'){
                    dfs(board,nx,ny,row,col,book);
                }
            }
        }
    }

## 岛屿的数量 ##

![c901d2237ab443d29a47219073dfe6cd.png][]

步骤

*  遍历矩阵,如果是陆地没有遍历过
 *  ret++,进入dfs
 *  dfs
    
     *  标记当前位置
     *  遍历四个方向
     *  得到新的坐标
     *  判断坐标是否合法
     *  如果是陆地没有遍历过
     *  进入下一个判断

class Solution {
        public int numIslands(char[][] grid) {
            int ret=0;
             int row=grid.length;
             int col=grid[0].length;
             int[][] book=new int[row][col];
             for(int i=0;i<row;i++){
                 for(int j=0;j<col;j++){
                     if(grid[i][j]=='1' && book[i][j]==0){
                         ret++;
                          dfs(grid,book,row,col,i,j);
                     }
                     
                 }
             }
             return ret;
           }
           int[][] next={
       {0,1},{0,-1},{1,0},{-1,0}};
           public void dfs(char[][] grid,int[][] book,int row,int col,int x,int y){
               book[x][y]=1;
               for(int i=0;i<4;i++){
                   int nx=x+next[i][0];
                   int ny=y+next[i][1];
    
                   if(nx>=row || nx<0 || ny>=col || ny<0){
                       continue;
                   }
    
                   if(grid[nx][ny]=='1' && book[nx][ny]==0){
                       dfs(grid,book,row,col,nx,ny);
                   }
               }
           }
    }

## 岛屿的最大面积 ##

![7dc798bdaa5f487ab750003e1c9b1eae.png][]

步骤

*  遍历数组,找到是陆地并且没有标记过的进入dfs
 *  dfs
    
     *  把当前位置标记
     *  遍历四个方向
     *  得到新的坐标
     *  判断坐标是否合法
     *  判断是否是陆地,是否遍历过-->进入递归,得到和
     *  返回和
 *  得到每一次和的最大值,返回

class Solution {
          public int maxAreaOfIsland(int[][] grid) {
            if(grid.length==0){
                return 0;
            }
            int row=grid.length;
            int col=grid[0].length;
            int[][] book=new int[row][col];
            int max=0;
            int ret=0;
            for(int i=0;i<row;i++){
                for(int j=0;j<col;j++){
                    if(book[i][j]==0 && grid[i][j]==1){
                        ret=dfs(grid,book,row,col,i,j);
                        max=Math.max(max,ret);
                    }
                }
            }
            return  max;
        }
    
        int[][] nextP={
       {0,1},{0,-1},{1,0},{-1,0}};
    
        private int dfs(int[][] grid, int[][] book, int row, int col, int x, int y) {
            book[x][y]=1;
            int r=1;
            for(int i=0;i<4;i++){
                int nx=x+nextP[i][0];
                int ny=y+nextP[i][1];
    
    
                if(nx>=row || nx<0 || ny>=col || ny<0){
                    continue;
                }
    
                if(grid[nx][ny]==1 && book[nx][ny]==0){
                    r+=dfs(grid,book,row,col,nx,ny);
                }
            }
            return r;
            
        }
    }

## 电话号码的字母组合 ##

## ![a89d499224424838be0fc73e679e79ff.png][] ##

步骤

*  把信息存放到字符串数组中,下标对应得到的数字
 *  边界:当前位置下标和字符串长度相等(遍历完),把字符串放入list中
 *  找到对应位置:通过当前下标,得到对应下标的数字,通过数字得到字符串数组中对应的字符串
 *  遍历字符串,进行下一个新的判断

public List<String> letterCombinations(String digits) {
        List<String> ret=new ArrayList<>();
        StringBuilder curStr=new StringBuilder("");
        dfs(digits,ret,curStr,0);
        //  数组 结果存放 当前字符串    遍历的长度
        return ret;
    
    }
    
    String[] mapString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    private void dfs(String digits, List<String> ret, StringBuilder curStr, int curDepth) {
       //边界
        if(curDepth==digits.length()){
            if(curStr.length()!=0){
                ret.add(curStr.toString());
            }
            return;
        }
        //找到对应位置
        int curMapIndex=digits.charAt(curDepth)-'0';//得到当前的数字
        String curMap=mapString[curMapIndex];//通过数字找到该下标的所有字母
        for (int i = 0; i < curMap.length(); i++) {
            //当前字符串加入新的字母(得到的字符串的每个元素依次遍历)
            dfs(digits, ret, curStr.append(curMap.charAt(i)), curDepth+1);
            //结束后,去掉新加的字母,为下一个字母的加入做准备
            curStr.deleteCharAt(curStr.length()-1);
        }
    }

## 二进制手表 ##

![1c3a277a2a85478882520404d85fd33f.png][]

步骤:

1. 判断边界 h>11 m>59 不满足

2.如果在边界上,还需要的灯的个数为0 时间放入list中

3.把十个灯遍历,得到对应的时间

class Solution {
        int[] hs={1,2,4,8,0,0,0,0,0,0};
        int[] ms={0,0,0,0,1,2,4,8,16,32};
        List<String> list=new ArrayList<>();
        public List<String> readBinaryWatch(int turnedOn) {
                 dfs(turnedOn,0,0,0);
                 return list;
        }
        public void dfs(int turnedOn,int index,int h,int m){
            if(h>11 || m>59){
                return ;
            }
            if(turnedOn==0){
                list.add(h+":"+(m<10?"0":"")+m);
            }
            for(int i=index;i<10;i++){
                dfs(turnedOn-1,i+1,h+hs[i],m+ms[i]);
            }
        }
    }

## 组合总和 ##

![1555cff30a3f4d76a694970b65d19eea.png][]

dfs:

等于目标返回

从当前位置到最后一个位置,遍历

如果当前位置的值大于目标值,continue

深度搜索

去掉最后一个元素

class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
           List<List<Integer>> solutions=new ArrayList<>();
           List<Integer> solution=new ArrayList<>();
           if(candidates.length==0){
               return solutions;
           }
           int curSum=0;
           dfs(solutions,solution,candidates,target,curSum,0);
           return solutions;
        }
        public static void dfs(List<List<Integer>> solutions,List<Integer> solution,int[] candidates,int target,int curSum,int index){
            if(curSum>=target){
                if(curSum==target){
                    List<Integer> newS=new ArrayList<>();
                    for(int e:solution){
                        newS.add(e);
                    }
                    solutions.add(newS);
                }
                return;
            }
            for(int i=index;i<candidates.length;i++){
                if(candidates[i]>target){
                    continue;
                }
                solution.add(candidates[i]);
                dfs(solutions,solution,candidates,target,curSum+candidates[i],i);
                solution.remove(solution.size()-1);
            }
    
        }
        
    }

## 活字印刷 ##

![200a4a88e2ae4c21adc8ec0794e8e2c1.png][]

因为每个只能使用一次,所有要标记是否使用过,如果没有使用过标记为0,进入遍历

dfs:

如果curStr长度不为0,放入set中

从0开始遍历titles

如果没有遍历过,标记为遍历,进入dfs,去到新加的,标记为没有遍历过

class Solution {
       public int numTilePossibilities(String tiles) {
            if(tiles.length()==0){
                return 0;
            }
            int[] book=new int[tiles.length()];
            Set<String> total=new HashSet<>();
            StringBuilder curStr=new StringBuilder();
            dfs(tiles,curStr,book,total);
            return total.size();
        }
    
        private void dfs(String tiles, StringBuilder curStr, int[] book, Set<String> total) {
            if(curStr.length()!=0){
                total.add(curStr.toString());
            }
            for(int i=0;i<tiles.length();i++){
                if(book[i]==0){
                    book[i]=1;
                    dfs(tiles,curStr.append(tiles.charAt(i)),book,total);
                    curStr.deleteCharAt(curStr.length()-1);
                    book[i]=0;
                }
            }
           
        }
    }

## N皇后 ##

![f06018bac8da489fb4eeb10bdaedc30f.png][]

dfs:

1.  判断是否遍历完,如果完成把结果存入solutions中
2.  遍历
    
    1.  判断是否冲突,不冲突,继续
    2.  把当前元素的位置存入solution中
    3.  进入下一个判断
    4.  回溯 去掉新加的元素

isVaild:判断列,行列和,行列差知否冲突,

transResult:

1.  遍历每一种方案
2.  创建一个List> ret
3.  把每一个都设置为.
4.  通过solution把对应位置设置为Q
5.  存入ret中

class pair{
        int x;
        int y;
        public pair(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
    public class Solution {
        public List<List<String>> solveNQueens(int n) {
           List<List<pair>> solutions=new ArrayList<>();
           List<pair> solution=new ArrayList();
           dfs(solutions,solution,0,n);
           return transResult(solutions,n);
        }
    
        private List<List<String>> transResult(List<List<pair>> solutions, int n) {
             //遍历每一个方案
            List<String> tmp=new ArrayList<>();
            //把每一种方案转换成string形式
            List<List<String>> ret=new ArrayList<>();
            for(List<pair> solution:solutions){
                List<StringBuilder> solutionString=new ArrayList<>();
    
                for(int i=0;i<n;i++) {
                    StringBuilder s = new StringBuilder();
                    //把所有的都设为.
                    for (int j = 0; j < n; j++) {
                        s.append('.');
                    }
                    solutionString.add(s);
                }
                    //通过solutions
                    for(pair p:solution){
                        solutionString.get(p.x).setCharAt(p.y,'Q');
                    }
                    List<String> curRet=new ArrayList<>();
                    for(StringBuilder s:solutionString){
                        curRet.add(s.toString());
                    }
                    ret.add(curRet);
                }
                return ret;
            }
    
    
    
        public void dfs(List<List<pair>> solutions,
                        List<pair> solution, int curRow, int n){
           if(curRow==n){
               List<pair> newS=new ArrayList<>();
               for(pair p:solution){
                   newS.add(p);
               }
               solutions.add(newS);
           }
    
           for(int i=0;i<n;i++){
               if(isVaild(solution,curRow,i)){
                   //判断列是否相同
                   //行每次会增加,不会冲突
                   solution.add(new pair(curRow,i));
                   dfs(solutions,solution,curRow+1,n);
                   solution.remove(solution.size()-1);
               }
           }
        }
    
        private boolean isVaild(List<pair> solution, int row, int col) {
           for(pair i:solution){
               if(i.y==col || i.x+i.y==row+col || i.x-i.y==row-col){
                   return false;
               }
           }
           return true;
        }
    }

[3347423c74d044469c30e4a1dd7db712.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/10dd7540022248c0956ba9e327cff370.png
[045a47b358bb47f5b7b9706e6192ff19.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/84e0234f31de413ebfc145a70a373bec.png
[8251a254aa4845e088a0fb5a07e5eca1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/a6d6b1083a9e48a4bcefcea9d633df1d.png
[a47e49e2d2fd40b1972e231eba897cb4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/dc3b1ff364b54ec2a7d5a124a1dd7ede.png
[c901d2237ab443d29a47219073dfe6cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/824b3af9f2ff461989a6064a4423e960.png
[7dc798bdaa5f487ab750003e1c9b1eae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/e77f933fd1d34cfbb26dda334956b8ab.png
[a89d499224424838be0fc73e679e79ff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/f05a2f98655b4ac2a81ea0d74fc3826d.png
[1c3a277a2a85478882520404d85fd33f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/1d625e13136f4b24ad1f943cea262993.png
[1555cff30a3f4d76a694970b65d19eea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/250acf40fb4349048b79b9002911246a.png
[200a4a88e2ae4c21adc8ec0794e8e2c1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/aaacf744d1434cca938e03f712202bb6.png
[f06018bac8da489fb4eeb10bdaedc30f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/af66a45cf3574de9abcd0806ca7f490f.png