devbox
weixin_40725706
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

穷举&&深搜&&暴搜&&回溯&&剪枝(3)

作者：weixin_40725706 | 2024-05-03 01:52:24

赞

踩

穷举&&深搜&&暴搜&&回溯&&剪枝(3)

一)字母大小写全排列

784. 字母大小写全排列 - 力扣（LeetCode）

1)从每一个字符开始进行枚举，如果枚举的是一个数字字符，直接忽视

如果是字母的话，进行选择是变还是不变

2)当进行遍历到叶子结点的时候，直接将结果存放到ret里面即可

3)相对于是对于这个决策树做一个深度优先遍历

dfs函数的设计:

1)无论是数字字符还是字母，都是需要考虑变或者不变的情况

2)当当前字符是一个非数字字符，此时就需要进行改变，然后进入下一层

  1. class Solution {
  2.     List<String> ret=new ArrayList<>();
  3.     StringBuilder path=new StringBuilder();
  4.     public List<String> letterCasePermutation(String s) {
  5.         char[] array=s.toCharArray();
  6.         dfs(array,0);
  7.         return ret;
  8.     }
  9.     public void dfs(char[] array,int index){
  10.         if(path.length()==array.length){
  11.             ret.add(path.toString());
  12.             return;
  13.         }
  14.         if(index>=array.length) return;
  15.     //选
  16.     if(array[index]>='0'&&array[index]<='9'){
  17.         path.append(array[index]);
  18.         dfs(array,index+1);
  19.         path.deleteCharAt(path.length()-1);
  20.     }else{
  21.        path.append(array[index]);
  22.        dfs(array,index+1);
  23.        path.deleteCharAt(path.length()-1);
  24.        if(array[index]>='a'&&array[index]<='z')
  25.            path.append((char)(array[index]-32));
  26.        else
  27.            path.append((char)(array[index]+32));
  28.        dfs(array,index+1);
  29.        path.deleteCharAt(path.length()-1);
  30.      }
  31.     }
  32. }
  1. class Solution {
  2.     StringBuilder path=new StringBuilder();
  3.     List<String> ret=new ArrayList<>();
  4.     public void dfs(char[] array,int index){
  5.         if(path.length()==array.length){
  6.             ret.add(path.toString());
  7.             return;
  8.         }
  9.             if(array[index]>='a'&&array[index]<='z'){
  10.                 path.append((char)(array[index]-32));
  11.                 dfs(array,index+1);
  12.                 path.deleteCharAt(path.length()-1);
  13.                   path.append((char)(array[index]));
  14.                 dfs(array,index+1);
  15.                 path.deleteCharAt(path.length()-1);
  16.             }else if(array[index]>='A'&&array[index]<='Z'){
  17.                 path.append((char)(array[index]+32));
  18.                 dfs(array,index+1);
  19.                 path.deleteCharAt(path.length()-1);
  20.                   path.append((char)(array[index]));
  21.                 dfs(array,index+1);
  22.                 path.deleteCharAt(path.length()-1);
  23.             }else{
  24.                 path.append(array[index]);
  25.                 dfs(array,index+1);
  26.                 path.deleteCharAt(path.length()-1);
  27.             }
  28.         }
  29.     public List<String> letterCasePermutation(String s) {
  30.         char[] array=s.toCharArray();
  31.         dfs(array,0);
  32.         return ret;
  33.  
  34.     }
  35. }

二)优美的排列

526. 优美的排列 - 力扣（LeetCode）

1)每一层就是相当于是数组的最终结果的每一个位置，开始就是从第一个数开始将数组中的所有的数进行枚举一遍，只要这个数没有使用过，就可以把这个数放在这里面试一试

2)还是需要判断一下这个数能否整除下标或者是能够被下标整除，只要上面的条件有一种情况不满足，那么就进行剪枝操作；

3)函数的递归出口:当遇到叶子节点的时候，直接返回结果

1)假设现在n=3，现在我们有1 2 3这三个数字，我们需要找到这三个数字的全排列，这三个数填到三个格子里面，然后判断一下哪一种填发使这个格子是一个优美的排列；

在第一个位置枚举1 2 3三个数，在第二个位置枚举1 2 3三个数，在第三个位置枚举1 2 3三个数，重复子问题就是在特定的下标开始枚举数组中所有的数

2)本质上在第一层枚举的过程中其实已经就进行了剪枝的操作了

3)此时我们先排第一个位置，然后再排第二个位置，最后排第三个位置

dfs函数的设计:每一层在做的事情:将数组中的数从头到尾进行枚举一遍，只要这个数没有被使用过或者是这个数可以整除下标或者能被下标整除，这个数就可以存放在这里

  1. class Solution {
  2.     List<List<Integer>> ret=new ArrayList<>();
  3.     List<Integer> path=new ArrayList<>();
  4.     boolean[] check;
  5.     public int countArrangement(int n) {
  6.        check=new boolean[n+1];//因为下标是从1开始所以要开辟n+1大小的数组
  7.        dfs(n,1);//从下标是1的位置开始进行枚举
  8.        return ret.size();
  9.     }
  10.     public void dfs(int n,int pos){
  11.         if(path.size()==n){
  12.             ret.add(new ArrayList<>(path));
  13.             return;
  14.         }
  15.       for(int i=1;i<=n;i++){
  16.           if((i%pos==0||pos%i==0)&&check[i]==false){
  17.               path.add(i);
  18.               check[i]=true;
  19.               dfs(n,pos+1);//枚举下一个位置的数
  20.               path.remove(path.size()-1);
  21.               check[i]=false;
  22.           }
  23.       }
  24.     }
  25. }

三)N皇后:

难点:剪枝+代码能力

51. N 皇后 - 力扣（LeetCode）

第一种画决策树的方法:

先考虑第一个格子能不能进行存放，当进行考虑下一个格子的时候，是进行挨着考虑的，一个格子一个格子看看能不能进行存放

第二种画决策树的方法:是通过一行一行的来进行考虑的

此时我不是一个格子一个格子的进行考虑，这一次我一次考虑一行，我只考虑第0行的皇后应该摆放在那里，应该只考虑第一行的皇后摆放在哪里，然后第二行的皇后应该摆放在那里，第三行的皇后应该摆放在那里，下面我们进行考虑一下当N=3的时候:

1)首先我们第一步应该考虑一下，第0行的皇后可以放在哪里，这个时候又出现三种情况可以放在(0，0)可以放在(0，1)，还可以放在(0，2)

2)然后再次进行考虑，当我们第0行的三个皇后已经放好的情况下，那么此时再来进行考虑第一行，正常情况下如果不出现剪枝的情况，第一行也是可以存放三个位置的分别是(1，0)，(1，1)和(1，2)，但是此时考虑剪枝，这个时候就出现了，某一个行上面有两个皇后，对角线上面有两个皇后

1)我们再进行画决策树的时候，先将皇后画在格子里面，再来进行判断是否要进行剪枝

2)每一层在做的事情:你给我一个行数，我在这一行内每一个格子尝试存放一个皇后，如果我能够存放，我就把这个皇后放在这里，然后进行考虑下一行，具体下一行如何放我并不关心，我只是关心的事dfs函数一定可以帮助我们搞定

3)递归出口VS收集结果:当我们枚举行数发生越界的时候，此时说明就已经得到了合法的情况，此时就可以把这个合法的情况加入到我们最终的结果中即可

如何剪枝:剪枝的目的就是考虑当前这个位置是否可以能够放上皇后

1)无脑循环:当我们进行判断这个位置是否可以放皇后的时候，先假设当前这个这个位置可以存放皇后，首先来判断这一行有没有放皇后，这一列有没有放皇后，这个皇后的左对角线有没有放皇后，这个皇后的右对角线有没有放皇后，时间复杂度是4n*2^n，某一个决策上来四层循环，在这种决策树的画法里面，我们是每一行每一行的来进行列举的，所以当我们进行列举这一行上面的三个位置的时候，是一定不会出现在这一行上面的，这一行是一定不会出现相互攻击的情况的

  1. class Solution {
  2.     List<List<String>> ret=new ArrayList<>();
  3.     public void GetString(char[][] array){
  4.        List<String> path=new ArrayList<>();
  5.         for(int i=0;i<array.length;i++){
  6.             StringBuilder result=new StringBuilder();
  7.             for(int j=0;j<array[0].length;j++){
  8.                 result.append(array[i][j]);
  9.             }
  10.             path.add(result.toString());
  11.         }
  12.      ret.add(new ArrayList<>(path));
  13.     }
  14.     public void dfs(char[][] array,int row,int n){
  15.         if(row==n){
  16.            GetString(array);
  17.            return;
  18.         }
  19.         for(int col=0;col<n;col++){
  20.             if(isVaild(array,row,col,n)==true){
  21.                 array[row][col]='Q';
  22.                 dfs(array,row+1,n);
  23.                 array[row][col]='.';
  24.             }
  25.         }
  26.     }
  27.     public boolean isVaild(char[][] array,int row,int col,int n){
  28.         //1.先检查列
  29.         for(int i=0;i<n;i++){
  30.             if(array[i][col]=='Q') return false;
  31.         }
  32.         // //2.在来进行检查行
  33.         // for(int i=0;i<n;i++){
  34.         //     if(array[][col]=='Q') return false;
  35.         // }
  36.         //3.检查45度对角线
  37.         for(int i=row,j=col;i>=0&&j>=0;i--,j--){
  38.             if(array[i][j]=='Q') return false;
  39.         }
  40.         //4.检查135度对角线
  41.         for(int i=row,j=col;i>=0&&j<=n-1;i--,j++){
  42.             if(array[i][j]=='Q') return false;
  43.         }
  44.         return true;
  45.     }
  46.  
  47.     public List<List<String>> solveNQueens(int n) {
  48.         char[][] array=new char[n][n];
  49.         int row=array.length;
  50.         int col=array[0].length;
  51.         for(int i=0;i<row;i++){
  52.             for(int j=0;j<col;j++){
  53.                 array[i][j]='.';
  54.             }
  55.         }
  56.     dfs(array,0,n);
  57.     return ret;
  58.     }
  59. }

2)类似于哈希表的策略:使用三个数组快速解决判断行列横对角线和竖行对角线

在这里面只是需要搞一个boolean数组就可以搞定这个题了

boolean checkcol[]=new boolean[n]，如果在第一列上放了一个皇后，那么只是需要让这一列变成true即可，那么就是checkcol[1]=true，说明这一列已经有皇后了，所以这个布尔数组使用布尔数组可以快速判断某一列是否有皇后了

3)判断对角线以及副对角线的策略:使用布尔数组+数学来进行解决

1)当我们的某一条线的y-x=b的时候，我们是有理由相信他这一条主对角线上面是有皇后的，因为这一条线上面的所有的纵坐标减去横坐标的值都是等于一个定值，如果对角线的boolean值是true，说明对角线上有皇后，如果这条线的boolean值是一个false，说明对角线上面没有皇后，也就是名这个点可能是可以放皇后的，但是使用y-x是不可以的

2)但是此时出现了一个致命的问题，原点下面的截距是一个负数，但是数组的下标是没有负数的，所以此时可以修改一下表达式y-x=b=>y-x+N=b+N，这样就做到了将所有的截距统一向上平移了N个单位，此时数组的下标一定是一个整数

  1. class Solution {
  2.     List<List<String>> ret=new ArrayList<>();
  3.     boolean[] checkCol;
  4.     boolean[] checkZline;
  5.     boolean[] checkFline;
  6.     //这个函数是将字符串数组中的所有字符转化成一个String存放到哈希表中
  7.     public void GetString(char[][] array){
  8.        List<String> path=new ArrayList<>();
  9.         for(int i=0;i<array.length;i++){
  10.             StringBuilder result=new StringBuilder();
  11.             for(int j=0;j<array[0].length;j++){
  12.                 result.append(array[i][j]);
  13.             }
  14.             path.add(result.toString());
  15.         }
  16.      ret.add(new ArrayList<>(path));
  17.     }
  18.     public void dfs(char[][] array,int row,int n){
  19.          if(row==n){
  20.            GetString(array);
  21.            return;
  22.         }
  23.         for(int col=0;col<n;col++){
  24. if(checkCol[col]==false&&checkFline[row+col]==false
  25. &&checkZline[col-row+n]==false){
  26.      checkCol[col]=true;
  27.      checkFline[row+col]=true;
  28.      checkZline[col-row+n]=true;
  29.     array[row][col]='Q';
  30.     dfs(array,row+1,n);
  31.      array[row][col]='.';
  32.      checkCol[col]=false;
  33.      checkFline[row+col]=false;
  34.      checkZline[col-row+n]=false;
  35. }
  36.         }
  37.  
  38.     }
  39.     public List<List<String>> solveNQueens(int n) {
  40.     //1.首先定义一个二维的棋盘,并且初始化里面的字符
  41.         this.checkCol=new boolean[2*n];
  42.         this.checkZline=new boolean[2*n];
  43.         this.checkFline=new boolean[2*n];
  44.         char[][] array=new char[n][n];
  45.         int row=array.length;
  46.         int col=array[0].length;
  47.         for(int i=0;i<row;i++){
  48.             for(int j=0;j<col;j++){
  49.                 array[i][j]='.';
  50.             }
  51.         }
  52.         dfs(array,0,n);
  53.         return ret;
  54.     }
  55. }

四)有效的数独:

36. 有效的数独 - 力扣（LeetCode）

1)1-9的数字只能出现一次，每一行不能出现重复的元素，每一列也是不能出现重复的元素的，况且在3X3矩阵中也是不能出现重复的元素的

2)接下来使用哈希表的思想来解决一下这个问题，创建一个row[9][10]表示的是一共有9行，里面存放10个大小范围，row[2][4]表示第二行里面是否出现了4这个数，如果这里面的值是true就表示出现过，如果是false就表示没有出现过

3)col[9][10]表示创建一个大小9列，里面存放数的大小范围就是10，col[7][9]表示第7竖列是否存在9这个数，如果是true表明出现过，如果是false表明没有出现过

4)创建一个三维数组:grad[3][3][10]

总结:所以我们只是需要创建3个布尔类型的数组就可以判断某一行是否出现过某一个数字重复，某一列是否出现过某一个数字重复，某一个小方格里面是否某一个数字出现重复，典型的是使用空间换时间的思想

  1. class Solution {
  2.     boolean[][] checkLine;//checkLine[i][data]判断第i行data这个数是否出现过
  3.     boolean[][] checkRow;//checkRow[j][data]判断第j列data这个数是否出现过
  4.     boolean[][][] checkBroad;
  5. //checkBroad[x/3][y/3][data]判断在指定的矩形范围内,data这个数是否出现过
  6.     public boolean isValidSudoku(char[][] array) {
  7.         this.checkLine=new boolean[9][10];
  8.         this.checkRow=new boolean[9][10];
  9.         this.checkBroad=new boolean[3][3][10];
  10.         for(int i=0;i<9;i++){
  11.             for(int j=0;j<9;j++){
  12.             if(array[i][j]!='.'){
  13.                    int data=array[i][j]-'0';
  14.   if(checkRow[i][data]==true||checkLine[j][data]==true||checkBroad[i/3][j/3][data]==true) return false;
  15.             checkRow[i][data]=true;
  16.             checkLine[j][data]=true;
  17.             checkBroad[i/3][j/3][data]=true;
  18.  
  19.             }
  20.             }
  21.         }
  22.     return true;
  23.     }
  24. }

五)解数独

37. 解数独 - 力扣（LeetCode）

算法原理:

主要还是画决策树，如何不重不漏地将所有的情况枚举到，直到找到最终的正确答案

1)首先我们直接遍历这个棋盘，当遍历到某一个空位置的时候，就直接向上面进行填数，直到将这个棋盘上面的所有格子全部填满的时候，就最终找到了最终结果，想想原来在一维数组那里，无论是在子集那道题还是全排列那道题，直接考虑某一个位置，考虑当前这个位置填1填2还是填3，当前这个位置填好之后再来进行考虑下一个位置填1填2还是填3，无非就是说将原来一维数组的形式搬到二维数组里面了

2)本质上来说就是给你二维数组的一个位置，判断这个位置是否能够填写1-9的数字，如果能填写就判断下一个位置，某一个位置是可以有9个分支的，因为可以填写9个不同类型的数字，但是最终的结果一定是有一些分支要被剪掉的，我们还是像上道题那样，快速地判断出当前这个位置如果填写某一个数是否合适了；

3)如果我们在画决策树的时候发现，有一个位置1-9的数字都无法填写成了，直接向上返回个false；

  1. class Solution {
  2.     boolean[][] checkLine;
  3.     boolean[][] checkRow;
  4.     boolean[][][] checkBroad;
  5.     public boolean dfs(char[][] board){
  6.         for(int i=0;i<9;i++){
  7.             for(int j=0;j<9;j++){
  8.                 if(board[i][j]!='.') continue;
  9.                 else{
  10. //直接进行填数
  11.             for(int k=1;k<=9;k++){
  12.               if(!checkLine[j][k]&&!checkRow[i][k]&&!checkBroad[i/3][j/3][k]){
  13.                       board[i][j]=(char)('0'+k);
  14.                       checkLine[j][k]=checkRow[i][k]=checkBroad[i/3][j/3][k]=true;
  15.                       if(dfs(board)) return true;
  16. //dfs函数是继续去填下一个位置,如果下一个位置填写失败,dfs(board)返回false,说明下一个位置填写123456789都是不行的
  17. //开始去尝试下一个数
  18.                       checkLine[j][k]=checkRow[i][k]=checkBroad[i/3][j/3][k]=false;
  19.                       board[i][j]='.';
  20.  
  21.                         }
  22.                     }
  23. //说明1-9数字都不行
  24.                     return false;
  25.                 }
  26.  
  27.             }
  28.         }
  29. //经过这两层for循环之后,程序既没有返回true也没有返回false,说明这个表格恰好填写完成,此时返回一个true即可
  30.         return true;
  31.     }
  32.     public void solveSudoku(char[][] board) {
  33. //1.先进行初始化操作
  34.         this.checkLine=new boolean[9][10];
  35.         this.checkRow=new boolean[9][10];
  36.         this.checkBroad=new boolean[3][3][10];
  37. //2.提前给这些数组进行赋值
  38.         for(int i=0;i<9;i++)
  39.             for(int j=0;j<9;j++)
  40.                 if(board[i][j]!='.'){
  41.                     int data=board[i][j]-'0';
  42.                     checkLine[j][data]=true;
  43.                     checkRow[i][data]=true;
  44.                     checkBroad[i/3][j/3][data]=true;
  45.                 }
  46. //3.进行设计dfs函数
  47.         dfs(board);
  48.     }
  49. }

1)本体求的是解数独问题，此时只是需要返回一个结果即可，之前的回溯算法的题目都是组合都是有多个结果，我们需要用一个结果集收集我们的所有结果然后返回即可，那些题目都是有多个结果，多个结果意味着这些结果都是散落在树形结构里面，所以我们需要搜索所有的树形结构，然后最终才能把我们想要的结果全部放入到结果集里面，最后返回即可，只要有一个解决方案，那么立即就返回

2)我们只是需要搜索到一个最终结果，其他树枝不搜了，所以本题的返回类型是一个布尔类型，只是做一个标记，这样才能在树枝上找到结果之后这样才能告诉上一层找到结果立即返回，想上一层一层进行返回，其他数层都不用搜索了，所以说搜索整个树形结构使用void，搜索单个树枝就使用布尔；

3)就比如说路经总和那道题，我们只是需要找到某一条路径和等于目标值即可，找到单个结果就立即返回，因为没有必要遍历所有的节点

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/527156
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号