一)單詞搜索:

直接在矩陣中依次找到特定字符串

79. 單詞搜索 - 力扣（LeetCode）

畫出決策樹，只需要做一個深度優(yōu)先遍歷:

1)設計dfs函數(shù):只需要關心每一層在做什么即可，從這個節(jié)點開始，開始去嘗試匹配字符串的下一個字符，就是從某一個位置的字符開始，上下左右下標看看能不能匹配下一個字符，給定一個節(jié)點的位置，上下左右去匹配一個結(jié)點的位置，dfs(char[][] board，i，j，s，pos)，把原始的矩陣給定，把這個字符的位置，把要匹配字符串，字符串匹配到哪一個位置

2)從i，j位置開始上下左右去搜索word的哪一個字符就可以了

3)boolean返回值代表此次路徑的選擇是成功還是失敗

2)二維矩陣中要注意的細節(jié)問題:

在二維矩陣搜索的過程中不能走重復的路，要想解決這個問題，可以有兩種方法:

2.1)使用一個和原始矩陣相同規(guī)模大小的布爾數(shù)組，如果這個字符已經(jīng)被路徑走過了，那么直接修改成true

2.2)直接修改原始矩陣的值，如果某一個字符被走過了，那么直接修改字符為.或者其他標記字符

假設在下面的這個例子中給定我們一個矩陣，給定一個字符串A="AAAA"判斷是否可以匹配成功

2.3)當我們第一次成功的匹配到了A字符的時候，將這個A字符標記成true，表示這個字符已經(jīng)被使用過了，此時想左匹配第二個A字符，當嘗試在第二個A字符中匹配第三個A字符的時候，此時是不能再繼續(xù)想左找第一個A字符了，此時因為第一個A字符已經(jīng)被使用過了

class Solution {
    public boolean[][] check;
    int row;
    int col;
//利用向量數(shù)組一個for循環(huán)搞定上下左右四個方向
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
 public boolean dfs(char[][] board,String word,int i,int j,int pos){
        if(pos==word.length()) return true;
        //當匹配到最后一個字符之后直接返回
        //接下來向上下走有去匹配word[pos];
        for(int k=0;k<4;k++){
//從這里面開始左每一層所做的事情,從(i,j)下標開始上下左右去匹配pos位置的字符
            int x=i+dx[k];
            int y=j+dy[k];
if(x>=0&&x<row&&y>=0&&y<col&&check[x][y]==false&&board[x][y]==word.charAt(pos))
{
    check[x][y]=true;
    if(dfs(board,word,x,y,pos+1)) return true;
    check[x][y]=false;
}
        }
        return false;//匹配失敗在這里面返回說明上下左右都匹配不到想要的字符
    }
//此時如果不加上返回值的話,那么匹配成功也是返回return;
//此時匹配失敗也就是說上下左右找不到特定字符也是返回return;此時主函數(shù)就不知道最終是返回true還是false的
    public boolean exist(char[][] board, String word) {
//1.先進行計算二維數(shù)組的行和列,初始化布爾數(shù)組
        this.row=board.length;
        this.col=board[0].length;
        this.check=new boolean[row][col];
//2.現(xiàn)在整個數(shù)組中找到字符串中第一個字符出現(xiàn)的位置,然后去嘗試匹配下一個字符
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(board[i][j]==word.charAt(0)){
//先進行遍歷整個矩陣直到我們找到第一個位置的時候才會向下進行搜索
                    check[i][j]=true;
                    if(dfs(board,word,i,j,1)==true) return true;
//判斷從這個位置開始嘗試是否正確
                    check[i][j]=false;
                }
            }
        }
//3.代碼走到這里說明所有枚舉的第一個位置都無法匹配s這個字符串,所以直接返回false
    return false;
    }
}

二)黃金礦工:

算法原理:

1)這個題和上一個題的起始dfs位置是存在著差別的，上一道題必須是從字符串的第一個位置開始才可以進行向下dfs，而這個題從上下左右邊界任意位置開始進行dfs都可以

2)開采過的位置不能再挖，0號位置不能再挖

3)枚舉所有位置為起點，進行爆搜

1219. 黃金礦工 - 力扣（LeetCode）

class Solution {
    int ret=0;
    int row=0;
    int col=0;
    public boolean[][] check;
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    public void dfs(int[][] array,int i,int j,int glod){
        glod+=array[i][j];
        ret=Math.max(glod,ret);
        for(int k=0;k<4;k++){
            int x=i+dx[k];
            int y=j+dy[k];
if(x>=0&&x<row&&y>=0&&y<col&&!check[x][y]&&array[x][y]!=0){
    check[x][y]=true;
    dfs(array,x,y,glod);
    check[x][y]=false;
}
        }
    }
    public int getMaximumGold(int[][] array) {
        this.row=array.length;
        this.col=array[0].length;
        this.check=new boolean[row][col];
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array[0].length;j++){
                if(array[i][j]==0) continue;
                else{
                    check[i][j]=true;
                    dfs(array,i,j,0);//這個二層循環(huán)的目的就是從每一個位置開始開始挖此時能獲取到的最大黃金數(shù)
                    check[i][j]=false;
                }
            }
        }
    return ret;
    }
}

三)不同路徑

算法原理:在矩陣中進行搜索，先找到1的位置，從這個起始位置開始進行深度優(yōu)先遍歷，然后進行判斷這條路徑是否合法即可，解決方法就是在進行向下遞歸的過程中使用count變量來記錄一下，從起始位置開始記錄一下行走步數(shù)，到達最終結(jié)果之后，再進行對比和實際要走的步數(shù)是否相同(整個數(shù)組0的個數(shù))

980. 不同路徑 III - 力扣（LeetCode）

class Solution {
    //這樣處理的目的就是我所走的所有路徑的格子數(shù)等于總的格子數(shù)
    public int step=2;//表示處理第一個數(shù)和最后一個數(shù)
    public boolean[][] check;
    public int row=0;
    public int col=0;
    public int count=1;//表示處理第一個數(shù)
    public int ret=0;
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    public void dfs(int[][] array,int i,int j){
        if(array[i][j]==2){
            if(step==count){
                System.out.println(ret);
               ret++;
            }
         return;
        }
        for(int k=0;k<4;k++){
            int x=i+dx[k];
            int y=j+dy[k];
if(x>=0&&x<row&&y>=0&&y<col&&!check[x][y]&&array[x][y]!=-1){
             check[x][y]=true;
             count++;
             dfs(array,x,y);
             count--;
             check[x][y]=false;
}
        }
    }
    public int uniquePathsIII(int[][] array) {
        this.row=array.length;
        this.col=array[0].length;
        this.check=new boolean[row][col];
//1.先進行處理整個方形格子中的0的個數(shù)
        int dx=0;
        int dy=0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(array[i][j]==0) step++;
                else if(array[i][j]==1){
                    dx=i;
                    dy=j;
                }
            }
        }
//2.先找到1的位置
      check[dx][dy]=true;
      dfs(array,dx,dy);
    return ret;
    }
}

四)遞增子序列

算法原理:

1)這個題的剪枝策略一共有兩步:

1.2)在同一層內(nèi)，相同的元素重復出現(xiàn)的要剪掉

1.3)在每一層內(nèi)進行枚舉，從pos+1的位置開始進行枚舉，防止使用到上一層已經(jīng)使用過的元素

1.3)在本層進行枚舉元素的時候，一定要比上一層的最后一個元素要大，但是如果path中沒有任何元素，那么就可以放心地向里面添加元素

491. 遞增子序列 - 力扣（LeetCode）

class Solution {
    List<List<Integer>> ret=new ArrayList<>();
    List<Integer> path=new ArrayList<>();
    public void dfs(int[] nums,int pos){
        if(path.size()>=2){
            ret.add(new ArrayList<>(path));
        }
HashSet<Integer> set=new HashSet<>();
//將本層的所有元素保存起來,防止重復
        for(int i=pos;i<nums.length;i++){
if((path.size()==0||path.get(path.size()-1)<=nums[i])&&!set.contains(nums[i])){
            path.add(nums[i]);
            set.add(nums[i]);
            dfs(nums,i+1);
            path.remove(path.size()-1);
}
           
        }
    }
    public List<List<Integer>> findSubsequences(int[] nums) {
        dfs(nums,0);
        return ret;
    }
}

五)分割回文串

131. 分割回文串 - 力扣（LeetCode）

1)什么是切割線？startIndex后面應該被切割的字符串的第一個位置，第一個分割線就是在startIndex第一個字符后面的

2)如何表示切割的子串的范圍？[startIndex，i]，i一開始等于startIndex，此時切割線在i所指向的字符的后面

class Solution {
    List<List<String>> ret=new ArrayList<>();
     boolean[][] dp=null;
    List<String> path=new ArrayList<>();
    public void dfs(String s,int startIndex){
        if(startIndex==s.length()){
            ret.add(new ArrayList<>(path));
            return;
        }
//注意單層遞歸的邏輯
        for(int i=startIndex;i<s.length();i++){
            if(dp[startIndex][i]==true){
//判斷當前選擇切割的這一段部分是否是回文串,如果不是回文串,那么當前位置作廢,直接進行剪枝操作
                path.add(s.substring(startIndex,i+1));
//此時這個分割線在i+1這個字符的后面
                dfs(s,i+1);
                path.remove(path.size()-1);
            }else{
                continue;
            }
        }
    }
    public List<List<String>> partition(String s) {
//1.首先創(chuàng)建一個dp表,dp[i][j]表示以i位置元素為起點,j位置字符為終點,是否這個子串是一個回文串
this.dp=new boolean[s.length()][s.length()];
 //從下到上,從走向右進行填表
    for(int i=s.length()-1;i>=0;i--){
         for(int j=i;j<s.length();j++){
            if(s.charAt(i)==s.charAt(j)){
                if(i==j) dp[i][j]=true;
                else if(i+1==j) dp[i][j]=true;
                else{
                    dp[i][j]=dp[i+1][j-1];
                 }
           }else{
              dp[i][j]=false;
            }
      }
  }
  //2.然后進行回溯操作
       dfs(s,0);
       return ret;
    }
}

六)復原IP地址

93. 復原 IP 地址 - 力扣（LeetCode）

一)題目解析:

1)什么是有效的IP地址呢？

1.1)首先這個IP地址的經(jīng)過逗號分割的單獨一個部分可以包含一個0，但是一個數(shù)字前面不能出現(xiàn)前導0，就比如說0.011.122.32

1.2)還有經(jīng)過逗號分割的每一個部分的值都是小于255的，例如192.168.1.455

1.3)如果給定的字符串中出現(xiàn)了非正整數(shù)字符的話，那么它本身也是一個非法的IP地址

所以本題我們不光要對字符串進行切割處理，還需要針對切割出來的每一個字符串要做一個合法性的判斷

二)算法原理:

dfs參數(shù)的設計:

1)在我們的dfs函數(shù)的參數(shù)里面有一個變量叫做startIndex，主要作用就是從本層開始當進入到下一層遞歸的時候要從剩下的字符串的哪一個位置開始進行切割

2)傳入應該被切割的字符串

3)要加入的IP地址的點的數(shù)量，其實這個IP地址的點的數(shù)量就決定了這顆決策樹的深度，決策樹的高度其實就是三就可以了，也沒有必要向下進行切割了，如果你繼續(xù)向下切割，那么只能會多增加逗點，此時這個IP地址固定不是一個合法的IP地址了

返回值:

還有當進入到遞歸出口的時候，要對最后一個字符串做合法性的判斷，如果這個最后一個字符串也合法，最后才可以加入到最終的結(jié)果集里面，這個判斷函數(shù)，數(shù)字前面不能有0，區(qū)間長度不能超過255，不能出現(xiàn)除了數(shù)字外的字符

dfs函數(shù)有就是每一層要做的事:

1)枚舉每一個切割線的位置進行切割，如果發(fā)現(xiàn)切割線切除的字符串不是一個合法的字符串，就沒有必要繼續(xù)向下進行深度優(yōu)先遍歷了，直接向上返回就可以了

2)如果發(fā)現(xiàn)被這個切割線的子串是一個合法的字符串(s.substring(startIndex，i+1)，那么就將這個字符串加入到path里面，同時開始進行枚舉下一層最后回到本層的時候別忘了恢復現(xiàn)場

3)注意本體有一道坑，這個num這個數(shù)應該寫在for循環(huán)的里面，因為num所傳遞的數(shù)可能已經(jīng)超過了整數(shù)可以表示的最大范圍；

class Solution {
    List<String> ret=new ArrayList<>();
    StringBuilder path=new StringBuilder();
    public int pointNum=0;
    //判斷字符串s在左閉右閉區(qū)間[start,end]區(qū)間內(nèi)是否合法
    public boolean isValid(String s,int start,int end){
        if(s.equals("")) return false;
        if(start>end) return false;
        //以0為開始的字符不合法
        if(s.charAt(start)=='0'&&start!=end) return false;
        int num=0;
        for(int i=start;i<=end;i++){
            if(s.charAt(i)>'9'||s.charAt(i)<'0') return false;
            num=num*10+(s.charAt(i)-'0');
        }
        if(num>255) return false;
        return true;
    }
    public void dfs(String s,int startIndex){
//1.處理遞歸出口
        if(pointNum==3){
//說明此時逗號數(shù)量是3,分割結(jié)束,此時判斷第四段字符串是否合法,如果合法就加入到result中
if(isValid(s,startIndex,s.length()-1)){
//將最后一個字符串加入到path中
             path.append(s.substring(startIndex,s.length()));
             ret.add(path.toString());
//恢復現(xiàn)場,注意這里面不是s.length()-1
             path.delete(startIndex+2,path.length()-1);
           }
        return; 
        }
//2.處理每一層所干的事
      for(int i=startIndex;i<s.length();i++){
          if(isValid(s,startIndex,i)){
              path.append(s.substring(startIndex,i+1));
              pointNum++;
              path.append(".");
              dfs(s,i+1);
              pointNum--;
              path.delete(startIndex+pointNum,i+pointNum+2);
          }
       }
    }
    public List<String> restoreIpAddresses(String s) {
       // if(s.length()>12) return ret;
        dfs(s,0);
        return ret;

    }
}

七)不同的二叉搜索樹

95. 不同的二叉搜索樹 II - 力扣（LeetCode）

算法原理:

1)本體是采取后序遍歷的方式來解決這道問題的文章來源地址http://www.zghlxwxcb.cn/news/detail-707041.html

class Solution {
    List<TreeNode> ret=new ArrayList<>();
    public List<TreeNode> dfs(int start,int end){
        List<TreeNode> list=new ArrayList<>();
        if(start>end) {
            list.add(null);
            return list;此時沒有數(shù)字,將null加入到結(jié)果集中
        }
        for(int idx=start;idx<=end;idx++){
//嘗試使用每一個數(shù)字作為根節(jié)點
//1.先找到所有可能的左子樹
            List<TreeNode> leftIndexs=dfs(start,idx-1);
//2.再找到所有可能的右子樹
            //做有根節(jié)點兩兩組合
            List<TreeNode> rightIndexs=dfs(idx+1,end);
            for(int i=0;i<leftIndexs.size();i++){
                for(int j=0;j<rightIndexs.size();j++){
                    TreeNode root=new TreeNode(idx);
                    root.left=leftIndexs.get(i);
                    root.right=rightIndexs.get(j);
                    list.add(root);
                }
            }
        }
        return list;
    }
    public List<TreeNode> generateTrees(int n) {
       
        return  dfs(1,n);
    }
}

到了這里，關于窮舉&&深搜&&暴搜&&回溯&&剪枝(4)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！