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

一)单词搜索:

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

79. 单词搜索 - 力扣（LeetCode）

画出决策树，只需要做一个深度优先遍历:

1)设计dfs函数:只需要关心每一层在做什么即可，从这个节点开始，开始去尝试匹配字符串的下一个字符，就是从某一个位置的字符开始，上下左右下标看看能不能匹配下一个字符，给定一个节点的位置，上下左右去匹配一个结点的位置，dfs(char[][] board，i，j，s，pos)，把原始的矩阵给定，把这个字符的位置，把要匹配字符串，字符串匹配到哪一个位置

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

3)boolean返回值代表此次路径的选择是成功还是失败

2)二维矩阵中要注意的细节问题:

在二维矩阵搜索的过程中不能走重复的路，要想解决这个问题，可以有两种方法:

2.1)使用一个和原始矩阵相同规模大小的布尔数组，如果这个字符已经被路径走过了，那么直接修改成true

2.2)直接修改原始矩阵的值，如果某一个字符被走过了，那么直接修改字符为.或者其他标记字符

假设在下面的这个例子中给定我们一个矩阵，给定一个字符串A="AAAA"判断是否可以匹配成功

2.3)当我们第一次成功的匹配到了A字符的时候，将这个A字符标记成true，表示这个字符已经被使用过了，此时想左匹配第二个A字符，当尝试在第二个A字符中匹配第三个A字符的时候，此时是不能再继续想左找第一个A字符了，此时因为第一个A字符已经被使用过了

class Solution {
    public boolean[][] check;
    int row;
    int col;
//利用向量数组一个for循环搞定上下左右四个方向
    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=0&&yfalse&&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;此时主函数就不知道最终是返回true还是false的
    public boolean exist(char[][] board, String word) {
//1.先进行计算二维数组的行和列,初始化布尔数组
        this.row=board.length;
        this.col=board[0].length;
        this.check=new boolean[row][col];
//2.现在整个数组中找到字符串中第一个字符出现的位置,然后去尝试匹配下一个字符
        for(int i=0;i
            for(int j=0;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=0&&y0){
    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
            for(int j=0;j0].length;j++){
                if(array[i][j]==0) continue;
                else{
                    check[i][j]=true;
                    dfs(array,i,j,0);//这个二层循环的目的就是从每一个位置开始开始挖此时能获取到的最大黄金数
                    check[i][j]=false;
                }
            }
        }
    return ret;
    }
}

三)不同路径

算法原理:在矩阵中进行搜索，先找到1的位置，从这个起始位置开始进行深度优先遍历，然后进行判断这条路径是否合法即可，解决方法就是在进行向下递归的过程中使用count变量来记录一下，从起始位置开始记录一下行走步数，到达最终结果之后，再进行对比和实际要走的步数是否相同(整个数组0的个数)

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

class Solution {
    //这样处理的目的就是我所走的所有路径的格子数等于总的格子数
    public int step=2;//表示处理第一个数和最后一个数
    public boolean[][] check;
    public int row=0;
    public int col=0;
    public int count=1;//表示处理第一个数
    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=0&&y1){
             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的个数
        int dx=0;
        int dy=0;
        for(int i=0;i
            for(int j=0;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)在同一层内，相同的元素重复出现的要剪掉

1.3)在每一层内进行枚举，从pos+1的位置开始进行枚举，防止使用到上一层已经使用过的元素

1.3)在本层进行枚举元素的时候，一定要比上一层的最后一个元素要大，但是如果path中没有任何元素，那么就可以放心地向里面添加元素

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

class Solution {
    List> ret=new ArrayList<>();
    List path=new ArrayList<>();
    public void dfs(int[] nums,int pos){
        if(path.size()>=2){
            ret.add(new ArrayList<>(path));
        }
HashSet set=new HashSet<>();
//将本层的所有元素保存起来,防止重复
        for(int i=pos;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> findSubsequences(int[] nums) {
        dfs(nums,0);
        return ret;
    }
}

五)分割回文串

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

1)什么是切割线？startIndex后面应该被切割的字符串的第一个位置，第一个分割线就是在startIndex第一个字符后面的

2)如何表示切割的子串的范围？[startIndex，i]，i一开始等于startIndex，此时切割线在i所指向的字符的后面

class Solution {
    List> ret=new ArrayList<>();
     boolean[][] dp=null;
    List 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
            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> partition(String s) {
//1.首先创建一个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
            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地址的经过逗号分割的单独一个部分可以包含一个0，但是一个数字前面不能出现前导0，就比如说0.011.122.32

1.2)还有经过逗号分割的每一个部分的值都是小于255的，例如192.168.1.455

1.3)如果给定的字符串中出现了非正整数字符的话，那么它本身也是一个非法的IP地址

所以本题我们不光要对字符串进行切割处理，还需要针对切割出来的每一个字符串要做一个合法性的判断

二)算法原理:

dfs参数的设计:

1)在我们的dfs函数的参数里面有一个变量叫做startIndex，主要作用就是从本层开始当进入到下一层递归的时候要从剩下的字符串的哪一个位置开始进行切割

2)传入应该被切割的字符串

3)要加入的IP地址的点的数量，其实这个IP地址的点的数量就决定了这颗决策树的深度，决策树的高度其实就是三就可以了，也没有必要向下进行切割了，如果你继续向下切割，那么只能会多增加逗点，此时这个IP地址固定不是一个合法的IP地址了

返回值:

还有当进入到递归出口的时候，要对最后一个字符串做合法性的判断，如果这个最后一个字符串也合法，最后才可以加入到最终的结果集里面，这个判断函数，数字前面不能有0，区间长度不能超过255，不能出现除了数字外的字符

dfs函数有就是每一层要做的事:

1)枚举每一个切割线的位置进行切割，如果发现切割线切除的字符串不是一个合法的字符串，就没有必要继续向下进行深度优先遍历了，直接向上返回就可以了

2)如果发现被这个切割线的子串是一个合法的字符串(s.substring(startIndex，i+1)，那么就将这个字符串加入到path里面，同时开始进行枚举下一层最后回到本层的时候别忘了恢复现场

3)注意本体有一道坑，这个num这个数应该写在for循环的里面，因为num所传递的数可能已经超过了整数可以表示的最大范围；

class Solution {
    List ret=new ArrayList<>();
    StringBuilder path=new StringBuilder();
    public int pointNum=0;
    //判断字符串s在左闭右闭区间[start,end]区间内是否合法
    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){
//说明此时逗号数量是3,分割结束,此时判断第四段字符串是否合法,如果合法就加入到result中
if(isValid(s,startIndex,s.length()-1)){
//将最后一个字符串加入到path中
             path.append(s.substring(startIndex,s.length()));
             ret.add(path.toString());
//恢复现场,注意这里面不是s.length()-1
             path.delete(startIndex+2,path.length()-1);
           }
        return; 
        }
//2.处理每一层所干的事
      for(int i=startIndex;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 restoreIpAddresses(String s) {
       // if(s.length()>12) return ret;
        dfs(s,0);
        return ret;
 
    }
}

七)不同的二叉搜索树

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

算法原理:

1)本体是采取后序遍历的方式来解决这道问题的

class Solution {
    List ret=new ArrayList<>();
    public List dfs(int start,int end){
        List list=new ArrayList<>();
        if(start>end) {
            list.add(null);
            return list;此时没有数字,将null加入到结果集中
        }
        for(int idx=start;idx<=end;idx++){
//尝试使用每一个数字作为根节点
//1.先找到所有可能的左子树
            List leftIndexs=dfs(start,idx-1);
//2.再找到所有可能的右子树
            //做有根节点两两组合
            List rightIndexs=dfs(idx+1,end);
            for(int i=0;i
                for(int j=0;j
                    TreeNode root=new TreeNode(idx);
                    root.left=leftIndexs.get(i);
                    root.right=rightIndexs.get(j);
                    list.add(root);
                }
            }
        }
        return list;
    }
    public List generateTrees(int n) {
       
        return  dfs(1,n);
    }
}