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

这篇具有很好参考价值的文章主要介绍了穷举&&深搜&&暴搜&&回溯&&剪枝(4)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一)单词搜索:

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

79. 单词搜索 - 力扣(LeetCode)

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

穷举&&深搜&&暴搜&&回溯&&剪枝(4),剪枝,linux,算法

穷举&&深搜&&暴搜&&回溯&&剪枝(4),剪枝,linux,算法

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

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

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

穷举&&深搜&&暴搜&&回溯&&剪枝(4),剪枝,linux,算法

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

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

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

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

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

穷举&&深搜&&暴搜&&回溯&&剪枝(4),剪枝,linux,算法

穷举&&深搜&&暴搜&&回溯&&剪枝(4),剪枝,linux,算法

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<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;此时主函数就不知道最终是返回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<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);//这个二层循环的目的就是从每一个位置开始开始挖此时能获取到的最大黄金数
                    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<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的个数
        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)在同一层内,相同的元素重复出现的要剪掉

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

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所指向的字符的后面

穷举&&深搜&&暴搜&&回溯&&剪枝(4),剪枝,linux,算法

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.首先创建一个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地址的经过逗号分割的单独一个部分可以包含一个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所传递的数可能已经超过了整数可以表示的最大范围;

穷举&&深搜&&暴搜&&回溯&&剪枝(4),剪枝,linux,算法

穷举&&深搜&&暴搜&&回溯&&剪枝(4),剪枝,linux,算法

class Solution {
    List<String> 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<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)本体是采取后序遍历的方式来解决这道问题的文章来源地址https://www.toymoban.com/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;此时没有数字,将null加入到结果集中
        }
        for(int idx=start;idx<=end;idx++){
//尝试使用每一个数字作为根节点
//1.先找到所有可能的左子树
            List<TreeNode> leftIndexs=dfs(start,idx-1);
//2.再找到所有可能的右子树
            //做有根节点两两组合
            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)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【leetcode】深搜、暴搜、回溯、剪枝(C++)2

    leetcode链接 leetcode链接 leetcode链接 全局变量的超时代码: 原因在于nums的长度最长有20,其2^20次方太大了。但是leetcode居然通过了。 path作为参数的正确代码: leetcode链接 解法一: 解法二: 解法一: 解法二: leetcode链接 leetcode链接 leetcode链接 这里我们着重在剪枝方面上面的

    2024年02月20日
    浏览(40)
  • DFS:深搜+回溯+剪枝解决组合问题

                                                   创作不易,感谢支持!!! . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) 该题和前面是类似的,但是用回溯算法,会超

    2024年04月12日
    浏览(39)
  • DFS:深搜+回溯+剪枝解决排列、子集问题

                                        创作不易,感谢三连支持!!  . - 力扣(LeetCode) . - 力扣(LeetCode)  方案1:不合法就continue 方案2:合法才能进循环 . - 力扣(LeetCode) . - 力扣(LeetCode)  策略1:决策树以选不选作为参考,结果为叶子节点 策略2:决策树以选几个

    2024年04月16日
    浏览(66)
  • DFS:深搜+回溯+剪枝解决矩阵搜索问题

                                                   创作不易,感谢三连!!  . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) 1、矩阵搜索问题经常要用到向量,也就是我们可以通过dx和dy来帮助我们定义方向

    2024年04月17日
    浏览(41)
  • 递归、搜索与回溯算法(专题二:深搜)

    往期文章(希望小伙伴们在看这篇文章之前,看一下往期文章) (1)递归、搜索与回溯算法(专题零:解释回溯算法中涉及到的名词)【回溯算法入门必看】-CSDN博客 (2)递归、搜索与回溯算法(专题一:递归)-CSDN博客  深搜是实现递归的一种方式,接下来我们之间从题

    2024年01月20日
    浏览(81)
  • Java中常用算法及示例-分治、迭代、递归、递推、动态规划、回溯、穷举、贪心

    1、分治算法的基本思想是将一个计算复杂的问题分成规模较小、计算简单的小问题求解, 然后综合各个小问题,得到最终答案。 2、穷举(又称枚举)算法的基本思想是从所有可能的情况中搜索正确的答案。 3、迭代法(Iterative Method) 无法使用公式一次求解,而需要使用重复结构

    2024年02月08日
    浏览(45)
  • 回溯算法例题(剪枝策略)

    链接: 77. 组合 链接: 216. 组合总和 III 链接: 17. 电话号码的字母组合 链接: 39. 组合总和 注:使用剪枝必须对原数组进行排序 链接: 40. 组合总和 II 链接: 131. 分割回文串 链接: 93. 复原 IP 地址 链接: 78. 子集 链接: 90. 子集 II 链接: 46. 全排列 链接: 47. 全排列 II 链接: 51. N 皇后 链接

    2024年02月04日
    浏览(90)
  • 【算法】递归、回溯、剪枝、dfs 算法题练习(组合、排列、总和问题;C++)

    后面的练习是接着下面链接中的文章所继续的,在对后面的题练习之前,可以先将下面的的文章进行了解👇: 【算法】{画决策树 + dfs + 递归 + 回溯 + 剪枝} 解决排列、子集问题(C++) 思路 题意分析 :要求根据给出的数字,算出合法的括号组成个数。根据题目,我们可以总

    2024年02月22日
    浏览(50)
  • 【算法】回溯:与递归,dfs的同质与分别,剪枝与恢复现场的详细理解,n皇后的回溯解法及算法复杂度分析。

    目录 ​编辑 1.什么是回溯 2.关于剪枝 3.关于恢复现场 4.题目:二叉树的所有路径(凸显恢复现场:切实感受回溯与深搜) 问题分析 ①函数设置为:void Dfs(root) ②函数设置为:void Dfs(root,path) 解题思想:使⽤深度优先遍历(DFS)求解。 代码实现 5.N后问题 问题分析 4皇后的放置

    2024年04月16日
    浏览(41)
  • 专题二:二叉树的深搜【递归、搜索、回溯】

    深度优先遍历 (DFS,全称为DepthFirstTraversal),是我们树或者图这样的数据结构中常用的⼀种遍历算法。这个算法会尽可能深的搜索树或者图的分⽀,直到⼀条路径上的所有节点都被遍历完毕,然后再回溯到上⼀层,继续找⼀条路遍历。 在⼆叉树中,常⻅的深度优先遍历为:

    2024年02月07日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包