一)字母大小寫全排列

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

1)從每一個(gè)字符開始進(jìn)行枚舉，如果枚舉的是一個(gè)數(shù)字字符，直接忽視

如果是字母的話，進(jìn)行選擇是變還是不變

2)當(dāng)進(jìn)行遍歷到葉子結(jié)點(diǎn)的時(shí)候，直接將結(jié)果存放到ret里面即可

3)相對(duì)于是對(duì)于這個(gè)決策樹做一個(gè)深度優(yōu)先遍歷

dfs函數(shù)的設(shè)計(jì):

1)無論是數(shù)字字符還是字母，都是需要考慮變或者不變的情況

2)當(dāng)當(dāng)前字符是一個(gè)非數(shù)字字符，此時(shí)就需要進(jìn)行改變，然后進(jìn)入下一層

class Solution {
    List<String> ret=new ArrayList<>();
    StringBuilder path=new StringBuilder();
    public List<String> letterCasePermutation(String s) {
        char[] array=s.toCharArray();
        dfs(array,0);
        return ret;
    }
    public void dfs(char[] array,int index){
        if(path.length()==array.length){
            ret.add(path.toString());
            return;
        }
        if(index>=array.length) return;
    //選
    if(array[index]>='0'&&array[index]<='9'){
        path.append(array[index]);
        dfs(array,index+1);
        path.deleteCharAt(path.length()-1);
    }else{
       path.append(array[index]);
       dfs(array,index+1);
       path.deleteCharAt(path.length()-1);
       if(array[index]>='a'&&array[index]<='z')
           path.append((char)(array[index]-32));
       else
           path.append((char)(array[index]+32));
       dfs(array,index+1);
       path.deleteCharAt(path.length()-1);
     }
    }
}

class Solution {
    StringBuilder path=new StringBuilder();
    List<String> ret=new ArrayList<>();
    public void dfs(char[] array,int index){
        if(path.length()==array.length){
            ret.add(path.toString());
            return;
        }
            if(array[index]>='a'&&array[index]<='z'){
                path.append((char)(array[index]-32));
                dfs(array,index+1);
                path.deleteCharAt(path.length()-1);
                  path.append((char)(array[index]));
                dfs(array,index+1);
                path.deleteCharAt(path.length()-1);
            }else if(array[index]>='A'&&array[index]<='Z'){
                path.append((char)(array[index]+32));
                dfs(array,index+1);
                path.deleteCharAt(path.length()-1);
                  path.append((char)(array[index]));
                dfs(array,index+1);
                path.deleteCharAt(path.length()-1);
            }else{
                path.append(array[index]);
                dfs(array,index+1);
                path.deleteCharAt(path.length()-1);
            }
        }
    public List<String> letterCasePermutation(String s) {
        char[] array=s.toCharArray();
        dfs(array,0);
        return ret;

    }
}

二)優(yōu)美的排列

526. 優(yōu)美的排列 - 力扣（LeetCode）

1)每一層就是相當(dāng)于是數(shù)組的最終結(jié)果的每一個(gè)位置，開始就是從第一個(gè)數(shù)開始將數(shù)組中的所有的數(shù)進(jìn)行枚舉一遍，只要這個(gè)數(shù)沒有使用過，就可以把這個(gè)數(shù)放在這里面試一試

2)還是需要判斷一下這個(gè)數(shù)能否整除下標(biāo)或者是能夠被下標(biāo)整除，只要上面的條件有一種情況不滿足，那么就進(jìn)行剪枝操作；

3)函數(shù)的遞歸出口:當(dāng)遇到葉子節(jié)點(diǎn)的時(shí)候，直接返回結(jié)果

1)假設(shè)現(xiàn)在n=3，現(xiàn)在我們有1 2 3這三個(gè)數(shù)字，我們需要找到這三個(gè)數(shù)字的全排列，這三個(gè)數(shù)填到三個(gè)格子里面，然后判斷一下哪一種填發(fā)使這個(gè)格子是一個(gè)優(yōu)美的排列；

在第一個(gè)位置枚舉1 2 3三個(gè)數(shù)，在第二個(gè)位置枚舉1 2 3三個(gè)數(shù)，在第三個(gè)位置枚舉1 2 3三個(gè)數(shù)，重復(fù)子問題就是在特定的下標(biāo)開始枚舉數(shù)組中所有的數(shù)

2)本質(zhì)上在第一層枚舉的過程中其實(shí)已經(jīng)就進(jìn)行了剪枝的操作了

3)此時(shí)我們先排第一個(gè)位置，然后再排第二個(gè)位置，最后排第三個(gè)位置

dfs函數(shù)的設(shè)計(jì):每一層在做的事情:將數(shù)組中的數(shù)從頭到尾進(jìn)行枚舉一遍，只要這個(gè)數(shù)沒有被使用過或者是這個(gè)數(shù)可以整除下標(biāo)或者能被下標(biāo)整除，這個(gè)數(shù)就可以存放在這里

class Solution {
    List<List<Integer>> ret=new ArrayList<>();
    List<Integer> path=new ArrayList<>();
    boolean[] check;
    public int countArrangement(int n) {
       check=new boolean[n+1];//因?yàn)橄聵?biāo)是從1開始所以要開辟n+1大小的數(shù)組
       dfs(n,1);//從下標(biāo)是1的位置開始進(jìn)行枚舉
       return ret.size();
    }
    public void dfs(int n,int pos){
        if(path.size()==n){
            ret.add(new ArrayList<>(path));
            return;
        }
      for(int i=1;i<=n;i++){
          if((i%pos==0||pos%i==0)&&check[i]==false){
              path.add(i);
              check[i]=true;
              dfs(n,pos+1);//枚舉下一個(gè)位置的數(shù)
              path.remove(path.size()-1);
              check[i]=false;
          }
      }
    }
}

三)N皇后:

難點(diǎn):剪枝+代碼能力

51. N 皇后 - 力扣（LeetCode）

第一種畫決策樹的方法:

先考慮第一個(gè)格子能不能進(jìn)行存放，當(dāng)進(jìn)行考慮下一個(gè)格子的時(shí)候，是進(jìn)行挨著考慮的，一個(gè)格子一個(gè)格子看看能不能進(jìn)行存放

第二種畫決策樹的方法:是通過一行一行的來進(jìn)行考慮的

此時(shí)我不是一個(gè)格子一個(gè)格子的進(jìn)行考慮，這一次我一次考慮一行，我只考慮第0行的皇后應(yīng)該擺放在那里，應(yīng)該只考慮第一行的皇后擺放在哪里，然后第二行的皇后應(yīng)該擺放在那里，第三行的皇后應(yīng)該擺放在那里，下面我們進(jìn)行考慮一下當(dāng)N=3的時(shí)候:

1)首先我們第一步應(yīng)該考慮一下，第0行的皇后可以放在哪里，這個(gè)時(shí)候又出現(xiàn)三種情況可以放在(0，0)可以放在(0，1)，還可以放在(0，2)

2)然后再次進(jìn)行考慮，當(dāng)我們第0行的三個(gè)皇后已經(jīng)放好的情況下，那么此時(shí)再來進(jìn)行考慮第一行，正常情況下如果不出現(xiàn)剪枝的情況，第一行也是可以存放三個(gè)位置的分別是(1，0)，(1，1)和(1，2)，但是此時(shí)考慮剪枝，這個(gè)時(shí)候就出現(xiàn)了，某一個(gè)行上面有兩個(gè)皇后，對(duì)角線上面有兩個(gè)皇后

1)我們?cè)龠M(jìn)行畫決策樹的時(shí)候，先將皇后畫在格子里面，再來進(jìn)行判斷是否要進(jìn)行剪枝

2)每一層在做的事情:你給我一個(gè)行數(shù)，我在這一行內(nèi)每一個(gè)格子嘗試存放一個(gè)皇后，如果我能夠存放，我就把這個(gè)皇后放在這里，然后進(jìn)行考慮下一行，具體下一行如何放我并不關(guān)心，我只是關(guān)心的事dfs函數(shù)一定可以幫助我們搞定

3)遞歸出口VS收集結(jié)果:當(dāng)我們枚舉行數(shù)發(fā)生越界的時(shí)候，此時(shí)說明就已經(jīng)得到了合法的情況，此時(shí)就可以把這個(gè)合法的情況加入到我們最終的結(jié)果中即可

如何剪枝:剪枝的目的就是考慮當(dāng)前這個(gè)位置是否可以能夠放上皇后

1)無腦循環(huán):當(dāng)我們進(jìn)行判斷這個(gè)位置是否可以放皇后的時(shí)候，先假設(shè)當(dāng)前這個(gè)這個(gè)位置可以存放皇后，首先來判斷這一行有沒有放皇后，這一列有沒有放皇后，這個(gè)皇后的左對(duì)角線有沒有放皇后，這個(gè)皇后的右對(duì)角線有沒有放皇后，時(shí)間復(fù)雜度是4n*2^n，某一個(gè)決策上來四層循環(huán)，在這種決策樹的畫法里面，我們是每一行每一行的來進(jìn)行列舉的，所以當(dāng)我們進(jìn)行列舉這一行上面的三個(gè)位置的時(shí)候，是一定不會(huì)出現(xiàn)在這一行上面的，這一行是一定不會(huì)出現(xiàn)相互攻擊的情況的

class Solution {
    List<List<String>> ret=new ArrayList<>();
    public void GetString(char[][] array){
       List<String> path=new ArrayList<>();
        for(int i=0;i<array.length;i++){
            StringBuilder result=new StringBuilder();
            for(int j=0;j<array[0].length;j++){
                result.append(array[i][j]);
            }
            path.add(result.toString());
        }
     ret.add(new ArrayList<>(path));
    }
    public void dfs(char[][] array,int row,int n){
        if(row==n){
           GetString(array);
           return;
        }
        for(int col=0;col<n;col++){
            if(isVaild(array,row,col,n)==true){
                array[row][col]='Q';
                dfs(array,row+1,n);
                array[row][col]='.';
            }
        }
    }
    public boolean isVaild(char[][] array,int row,int col,int n){
        //1.先檢查列
        for(int i=0;i<n;i++){
            if(array[i][col]=='Q') return false;
        }
        // //2.在來進(jìn)行檢查行
        // for(int i=0;i<n;i++){
        //     if(array[][col]=='Q') return false;
        // }
        //3.檢查45度對(duì)角線
        for(int i=row,j=col;i>=0&&j>=0;i--,j--){
            if(array[i][j]=='Q') return false;
        }
        //4.檢查135度對(duì)角線
        for(int i=row,j=col;i>=0&&j<=n-1;i--,j++){
            if(array[i][j]=='Q') return false;
        }
        return true;
    }

    public List<List<String>> solveNQueens(int n) {
        char[][] array=new char[n][n];
        int row=array.length;
        int col=array[0].length;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                array[i][j]='.';
            }
        }
    dfs(array,0,n);
    return ret;
    }
}

2)類似于哈希表的策略:使用三個(gè)數(shù)組快速解決判斷行列橫對(duì)角線和豎行對(duì)角線

在這里面只是需要搞一個(gè)boolean數(shù)組就可以搞定這個(gè)題了

boolean checkcol[]=new boolean[n]，如果在第一列上放了一個(gè)皇后，那么只是需要讓這一列變成true即可，那么就是checkcol[1]=true，說明這一列已經(jīng)有皇后了，所以這個(gè)布爾數(shù)組使用布爾數(shù)組可以快速判斷某一列是否有皇后了

3)判斷對(duì)角線以及副對(duì)角線的策略:使用布爾數(shù)組+數(shù)學(xué)來進(jìn)行解決

1)當(dāng)我們的某一條線的y-x=b的時(shí)候，我們是有理由相信他這一條主對(duì)角線上面是有皇后的，因?yàn)檫@一條線上面的所有的縱坐標(biāo)減去橫坐標(biāo)的值都是等于一個(gè)定值，如果對(duì)角線的boolean值是true，說明對(duì)角線上有皇后，如果這條線的boolean值是一個(gè)false，說明對(duì)角線上面沒有皇后，也就是名這個(gè)點(diǎn)可能是可以放皇后的，但是使用y-x是不可以的

2)但是此時(shí)出現(xiàn)了一個(gè)致命的問題，原點(diǎn)下面的截距是一個(gè)負(fù)數(shù)，但是數(shù)組的下標(biāo)是沒有負(fù)數(shù)的，所以此時(shí)可以修改一下表達(dá)式y(tǒng)-x=b=>y-x+N=b+N，這樣就做到了將所有的截距統(tǒng)一向上平移了N個(gè)單位，此時(shí)數(shù)組的下標(biāo)一定是一個(gè)整數(shù)

class Solution {
    List<List<String>> ret=new ArrayList<>();
    boolean[] checkCol;
    boolean[] checkZline;
    boolean[] checkFline;
    //這個(gè)函數(shù)是將字符串?dāng)?shù)組中的所有字符轉(zhuǎn)化成一個(gè)String存放到哈希表中
    public void GetString(char[][] array){
       List<String> path=new ArrayList<>();
        for(int i=0;i<array.length;i++){
            StringBuilder result=new StringBuilder();
            for(int j=0;j<array[0].length;j++){
                result.append(array[i][j]);
            }
            path.add(result.toString());
        }
     ret.add(new ArrayList<>(path));
    }
    public void dfs(char[][] array,int row,int n){
         if(row==n){
           GetString(array);
           return;
        }
        for(int col=0;col<n;col++){
if(checkCol[col]==false&&checkFline[row+col]==false
&&checkZline[col-row+n]==false){
     checkCol[col]=true;
     checkFline[row+col]=true;
     checkZline[col-row+n]=true;
    array[row][col]='Q';
    dfs(array,row+1,n);
     array[row][col]='.';
     checkCol[col]=false;
     checkFline[row+col]=false;
     checkZline[col-row+n]=false;
}
        }

    }
    public List<List<String>> solveNQueens(int n) {
    //1.首先定義一個(gè)二維的棋盤,并且初始化里面的字符
        this.checkCol=new boolean[2*n];
        this.checkZline=new boolean[2*n];
        this.checkFline=new boolean[2*n];
        char[][] array=new char[n][n];
        int row=array.length;
        int col=array[0].length;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                array[i][j]='.';
            }
        }
        dfs(array,0,n);
        return ret;
    }
}

四)有效的數(shù)獨(dú):

36. 有效的數(shù)獨(dú) - 力扣（LeetCode）

1)1-9的數(shù)字只能出現(xiàn)一次，每一行不能出現(xiàn)重復(fù)的元素，每一列也是不能出現(xiàn)重復(fù)的元素的，況且在3X3矩陣中也是不能出現(xiàn)重復(fù)的元素的

2)接下來使用哈希表的思想來解決一下這個(gè)問題，創(chuàng)建一個(gè)row[9][10]表示的是一共有9行，里面存放10個(gè)大小范圍，row[2][4]表示第二行里面是否出現(xiàn)了4這個(gè)數(shù)，如果這里面的值是true就表示出現(xiàn)過，如果是false就表示沒有出現(xiàn)過

3)col[9][10]表示創(chuàng)建一個(gè)大小9列，里面存放數(shù)的大小范圍就是10，col[7][9]表示第7豎列是否存在9這個(gè)數(shù)，如果是true表明出現(xiàn)過，如果是false表明沒有出現(xiàn)過

4)創(chuàng)建一個(gè)三維數(shù)組:grad[3][3][10]

總結(jié):所以我們只是需要?jiǎng)?chuàng)建3個(gè)布爾類型的數(shù)組就可以判斷某一行是否出現(xiàn)過某一個(gè)數(shù)字重復(fù)，某一列是否出現(xiàn)過某一個(gè)數(shù)字重復(fù)，某一個(gè)小方格里面是否某一個(gè)數(shù)字出現(xiàn)重復(fù)，典型的是使用空間換時(shí)間的思想

class Solution {
    boolean[][] checkLine;//checkLine[i][data]判斷第i行data這個(gè)數(shù)是否出現(xiàn)過
    boolean[][] checkRow;//checkRow[j][data]判斷第j列data這個(gè)數(shù)是否出現(xiàn)過
    boolean[][][] checkBroad;
//checkBroad[x/3][y/3][data]判斷在指定的矩形范圍內(nèi),data這個(gè)數(shù)是否出現(xiàn)過
    public boolean isValidSudoku(char[][] array) {
        this.checkLine=new boolean[9][10];
        this.checkRow=new boolean[9][10];
        this.checkBroad=new boolean[3][3][10];
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
            if(array[i][j]!='.'){
                   int data=array[i][j]-'0';
  if(checkRow[i][data]==true||checkLine[j][data]==true||checkBroad[i/3][j/3][data]==true) return false;
            checkRow[i][data]=true;
            checkLine[j][data]=true;
            checkBroad[i/3][j/3][data]=true;

            }
            }
        }
    return true;
    }
}

五)解數(shù)獨(dú)

37. 解數(shù)獨(dú) - 力扣（LeetCode）

算法原理:

主要還是畫決策樹，如何不重不漏地將所有的情況枚舉到，直到找到最終的正確答案

1)首先我們直接遍歷這個(gè)棋盤，當(dāng)遍歷到某一個(gè)空位置的時(shí)候，就直接向上面進(jìn)行填數(shù)，直到將這個(gè)棋盤上面的所有格子全部填滿的時(shí)候，就最終找到了最終結(jié)果，想想原來在一維數(shù)組那里，無論是在子集那道題還是全排列那道題，直接考慮某一個(gè)位置，考慮當(dāng)前這個(gè)位置填1填2還是填3，當(dāng)前這個(gè)位置填好之后再來進(jìn)行考慮下一個(gè)位置填1填2還是填3，無非就是說將原來一維數(shù)組的形式搬到二維數(shù)組里面了

2)本質(zhì)上來說就是給你二維數(shù)組的一個(gè)位置，判斷這個(gè)位置是否能夠填寫1-9的數(shù)字，如果能填寫就判斷下一個(gè)位置，某一個(gè)位置是可以有9個(gè)分支的，因?yàn)榭梢蕴顚?個(gè)不同類型的數(shù)字，但是最終的結(jié)果一定是有一些分支要被剪掉的，我們還是像上道題那樣，快速地判斷出當(dāng)前這個(gè)位置如果填寫某一個(gè)數(shù)是否合適了；

3)如果我們?cè)诋嫑Q策樹的時(shí)候發(fā)現(xiàn)，有一個(gè)位置1-9的數(shù)字都無法填寫成了，直接向上返回個(gè)false；

class Solution {
    boolean[][] checkLine;
    boolean[][] checkRow;
    boolean[][][] checkBroad;
    public boolean dfs(char[][] board){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]!='.') continue;
                else{
//直接進(jìn)行填數(shù)
            for(int k=1;k<=9;k++){
              if(!checkLine[j][k]&&!checkRow[i][k]&&!checkBroad[i/3][j/3][k]){
                      board[i][j]=(char)('0'+k);
                      checkLine[j][k]=checkRow[i][k]=checkBroad[i/3][j/3][k]=true;
                      if(dfs(board)) return true;
//dfs函數(shù)是繼續(xù)去填下一個(gè)位置,如果下一個(gè)位置填寫失敗,dfs(board)返回false,說明下一個(gè)位置填寫123456789都是不行的
//開始去嘗試下一個(gè)數(shù)
                      checkLine[j][k]=checkRow[i][k]=checkBroad[i/3][j/3][k]=false;
                      board[i][j]='.';

                        }
                    }
//說明1-9數(shù)字都不行
                    return false;
                }

            }
        }
//經(jīng)過這兩層for循環(huán)之后,程序既沒有返回true也沒有返回false,說明這個(gè)表格恰好填寫完成,此時(shí)返回一個(gè)true即可
        return true;
    }
    public void solveSudoku(char[][] board) {
//1.先進(jìn)行初始化操作
        this.checkLine=new boolean[9][10];
        this.checkRow=new boolean[9][10];
        this.checkBroad=new boolean[3][3][10];
//2.提前給這些數(shù)組進(jìn)行賦值
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
                if(board[i][j]!='.'){
                    int data=board[i][j]-'0';
                    checkLine[j][data]=true;
                    checkRow[i][data]=true;
                    checkBroad[i/3][j/3][data]=true;
                }
//3.進(jìn)行設(shè)計(jì)dfs函數(shù)
        dfs(board);
    }
}

1)本體求的是解數(shù)獨(dú)問題，此時(shí)只是需要返回一個(gè)結(jié)果即可，之前的回溯算法的題目都是組合都是有多個(gè)結(jié)果，我們需要用一個(gè)結(jié)果集收集我們的所有結(jié)果然后返回即可，那些題目都是有多個(gè)結(jié)果，多個(gè)結(jié)果意味著這些結(jié)果都是散落在樹形結(jié)構(gòu)里面，所以我們需要搜索所有的樹形結(jié)構(gòu)，然后最終才能把我們想要的結(jié)果全部放入到結(jié)果集里面，最后返回即可，只要有一個(gè)解決方案，那么立即就返回

2)我們只是需要搜索到一個(gè)最終結(jié)果，其他樹枝不搜了，所以本題的返回類型是一個(gè)布爾類型，只是做一個(gè)標(biāo)記，這樣才能在樹枝上找到結(jié)果之后這樣才能告訴上一層找到結(jié)果立即返回，想上一層一層進(jìn)行返回，其他數(shù)層都不用搜索了，所以說搜索整個(gè)樹形結(jié)構(gòu)使用void，搜索單個(gè)樹枝就使用布爾；

3)就比如說路經(jīng)總和那道題，我們只是需要找到某一條路徑和等于目標(biāo)值即可，找到單個(gè)結(jié)果就立即返回，因?yàn)闆]有必要遍歷所有的節(jié)點(diǎn)文章來源地址http://www.zghlxwxcb.cn/news/detail-632781.html

到了這里，關(guān)于窮舉&&深搜&&暴搜&&回溯&&剪枝(3)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！