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

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

一)电话号码的字母组合

17. 电话号码的字母组合 - 力扣(LeetCode)

1)画出决策树:只是需要对最终的决策树做一个深度优先遍历,在叶子节点收集结果即可

把图画出来,知道每一层在干什么,代码就能写出来了

 2)定义全局变量:

1)定义一个哈希表来处理数字和字符串的映射关系

2)使用ret来保存最终结果

class Solution {
    HashMap<Character,String> result=new HashMap<>();
    List<String> ret;
    StringBuilder path;
    public List<String> letterCombinations(String digits) {
        this.path=new StringBuilder();
        result.put('2',"abc");
        result.put('3', "def");
        result.put('4', "ghi");
        result.put('5', "jkl");
        result.put('6', "mno");
        result.put('7', "pqrs");
        result.put('8', "tuv");
        result.put('9', "wxyz");
        this.ret=new ArrayList<>();
        if(digits.length()==0){
            return ret;
        }
    dfs(result,digits,0);
    return ret;
    }
public void dfs(HashMap<Character,String> result,String digits,int index){
        if(index==digits.length()){
//这个最终条件,第一次就写错了,index遍历到数组的最后一个位置以后,说明当前已经把所有的字母枚举完成了
            ret.add(path.toString());
            return;
        }
       Character number=digits.charAt(index);
       String string=result.get(number);
       char[] chars=string.toCharArray();
       for(int i=0;i<chars.length;i++){
           path.append(chars[i]);
//继续遍历到下一层
           dfs(result,digits,index+1);
//恢复现场,回退到上一层
           path.deleteCharAt(path.length()-1);
       }
    }
}

二)括号生成:

22. 括号生成 - 力扣(LeetCode)

先进行想一下,什么是有效的括号组合?

1)左括号的数量==右括号的数量

2)从头开始的任意一个子串中,左括号的数量都是大于等于右括号的数量,如果发现右括号的数量是大于左括号的,那么必然会出现一个右括号没有做括号匹配,所以就不是一个有效的括号组合

假设如果n==3,那么我们只是需要枚举6个位置即可,因为n==3表示的是三对括号,一共有6个位置,那么我们只是需要进行暴力枚举6个位置可能出现的情况就可以了

一)画出决策树:

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

穷举&&深搜&&暴搜&&回溯&&剪枝(2),剪枝,linux,算法 二)定义一个全局变量: 

1)left表示左括号的数量,right表示右括号的数量,N表示一共有多少对括号

2)当进行深度优先遍历的时候,使用这个path变量来进行记录这个路径中曾经出现选择过的括号

三)dfs所干的事:

当左括号合法的时候,把左括号添加到path中当右括号合法的时候,把右括号添加到path中

四)递归:遇到叶子节点的时候,将这个path添加到ret中,遇到叶子节点的情况就是当right==N的时候,说明此时右括号已经满了

剪枝:

1)在进行遍历的过程中发现右括号的数量已经大于等于左括号了,此时能不能进行添加右括号了,应该进行剪枝操作

2)在进行遍历的过程中发现左括号的数量已经大于等于n了,此时不能再进行添加左括号了,进行剪枝操作

class Solution {
    int N;
    StringBuilder path;
    List<String> ret;//存放最终的结果字符串
    int right=0;//记录在深度优先遍历的过程中右括号的数量
    int left=0;//记录在深度优先遍历的过程中左括号的数量
    public List<String> generateParenthesis(int n) {
        N=n;
        path=new StringBuilder();
        ret=new ArrayList<>();
        dfs();
        return ret;
    }
    public void dfs(){
         if(right==N){
             ret.add(path.toString());
             return;
         }
    //选择左括号
    if(left<N){
         path.append('(');
         left++;
         dfs();
         //回溯恢复现场
         left--;
         path.deleteCharAt(path.length()-1);
      }
//选择右括号
    if(right<left){
        path.append(')');
        right++;
        dfs();
        //回溯恢复现场
        right--;
        path.deleteCharAt(path.length()-1);
    }
    }
}

其实本质上来说把刚才的那些全局变量放到参数里面,只是回溯时候的操作是不一样的

三)组合:

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

1)实现剪枝的操作:当我们进行枚举当前数的时候,只需要从当前数的下一个数字开始进行枚举就可以了,只需要控制dfs的参数即可

2)dfs做的事:从pos位置开始进行枚举,将枚举的情况添加到path中即可

3)回溯:当枚举完成当前位置向上归的过程中,先把path中添加的数进行剔除,然后再返回到上一层即可

4)递归出口:k==path.size()

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

class Solution {
    List<List<Integer>> ret;
    List<Integer> path;
    int N;
    int k;
    public List<List<Integer>> combine(int n, int k) {
        N=n;
        this.k=k;
        path=new ArrayList<>();
        ret=new ArrayList<>();
        dfs(1);
       return ret;
    }
    public void dfs(int index){
         if(path.size()==k) {
            ret.add(new ArrayList<>(path));
            return;
        }
    for(int i=index;i<=N;i++){
        path.add(i);
        dfs(i+1);
        path.remove(path.size()-1);
    }
    }
}

四)目标和

494. 目标和 - 力扣(LeetCode)

中心思想:

1)就是在第一个数前面+1或者是进行-1操作,变量作为全局变量还是函数中的参数来说,作为全局变量是需要考虑一下回溯,作为参数的话是不需要进行考虑回溯操作的,因为代码本身已经帮助我们递归向下进行向上返回的过程中已经帮助我们完成回溯操作了

2)当作为参数的时候,递归函数本身归的过程中已经在帮助我们进行回溯操作了,当int结果作为参数,数组类型或者是list类型作为全局的时候写法是比较方便的

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

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

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

此时index==5,正好最终的所有情况的和都是已经计算完成了,所以此时应该向上返回结果

class Solution {
    int count=0;
    int target=0;
    int path=0;
    public int findTargetSumWays(int[] nums, int target) {
        this.target=target;
        dfs(nums,0);
        return count;
    }
    public void dfs(int[] nums,int pos){
        if(pos==nums.length){
//path是标识这个路径中所选择的结果
            if(path==target) count++;
            return;
        }
//当前这个数取正数的情况
        path+=nums[pos];//pos的作用是记录数组下标
        dfs(nums,pos+1);
        //回溯
        path-=nums[pos];
//当前这个数取负数的情况
        path-=nums[pos];
        dfs(nums,pos+1);
        //回溯
        path+=nums[pos];
    }
}
class Solution {
    int count=0;
    int target=0;
    public int findTargetSumWays(int[] nums, int target) {
        this.target=target;
        dfs(nums,0,0);
        return count;
    }
   public void dfs(int[] nums,int path,int pos){
         if(pos==nums.length){
             if(path==target){
                 count++;
             }
             return;
         }
         dfs(nums,path+nums[pos],pos+1);//回来的就是原来的现场
         dfs(nums,path-nums[pos],pos+1);
   }
}

五)组合总和(1):

39. 组合总和 - 力扣(LeetCode)

1)没有一成不变的模板,只需要将决策树画出来,将最终的决策树转化成代码即可

2)反正这个题就是你从目标的元素里面找到几个数这几个数进行相加的结果等于target即可

3)所以这个题的中心思想就是一个数一个数,两个数,两个数的进行考虑

4)第一个位置可以存放2,可以存放3,可以存放5

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

解法1: 
穷举&&深搜&&暴搜&&回溯&&剪枝(2),剪枝,linux,算法穷举&&深搜&&暴搜&&回溯&&剪枝(2),剪枝,linux,算法

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

class Solution {
    List<List<Integer>> ret;
    int sum=0;
    List<Integer> path;
    int target=0;
    public List<List<Integer>> combinationSum(int[] nums, int target) {
        ret=new ArrayList<>();
        path=new ArrayList<>();
        this.target=target;
        Arrays.sort(nums);
        dfs(nums,0);
        return ret;
    }
    public void dfs(int[] nums,int index){
        if(sum==target){
            ret.add(new ArrayList<>(path));
            return;
        }
//index这个参数表示的是这一层循环从数组中的哪一个位置开始进行枚举
    for(int i=index;i<nums.length;i++){
        path.add(nums[i]);
        sum+=nums[i];
         if(sum>target){
             sum-=nums[i];
             path.remove(path.size()-1);
//如果说当前的数加起来的和已经都大于target了,那么后续都无需进行遍历了,因为此时数组是有序的,直接回退到上一层即可
             return;
         } 
        dfs(nums,i);//下一次遍历的位置还是可以从当前位置开始进行遍历,这里面是可以选择重复元素
        sum-=nums[i];
        path.remove(path.size()-1);
    }
 }
}
class Solution {
    List<List<Integer>> ret;
    int sum=0;
    List<Integer> path;
    int target=0;
    public List<List<Integer>> combinationSum(int[] nums, int target) {
        ret=new ArrayList<>();
        path=new ArrayList<>();
        this.target=target;
        Arrays.sort(nums);
        dfs(nums,0);
        return ret;
    }
    public void dfs(int[] nums,int index){
        if(sum>target) return;
        if(sum==target){
            ret.add(new ArrayList<>(path));
            return;
        }
    for(int i=index;i<nums.length;i++){
        path.add(nums[i]);
        sum+=nums[i];
        dfs(nums,i);
//枚举到下一层的时候回溯到当前结点的时候进行恢复现场的操作
        sum-=nums[i];
        path.remove(path.size()-1);
    }
 }
}

下面是当sum是局部变量的时候,所进行传递的值:

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

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

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

 解法2:根据选取对应的数的个数来画出决策树:

每一个数我可以选择0个,1个,可以选择2个,可以选择3个,可以选择4个

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

我们告诉dfs一个位置,枚举1个,两个,三个,只要小于8即可,只要枚举的个数*这个数<8即可,添加到path路径中,接下来去下一层开始走

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

当我们枚举完9的时候才会向上恢复现场的,因为假设如果枚举到3的时候才向上恢复现场,那么6的情况必定会被丢弃掉,因为后面的数是在前面的数的基础上+3的,后面的数要依赖于前面的数,所以当我们将这一层的所有的数处理完成之后才会恢复现场

class Solution {
    List<Integer> path=new ArrayList<>();
    List<List<Integer>> ret=new ArrayList<>();
    public int target;
    int sum=0;
    public void dfs(int[] nums,int index){
        if(sum==target){
            ret.add(new ArrayList<>(path));
            return;
        }
        if(index==nums.length||sum>target) return;
        //进行枚举nums[index]使用多少个
        for(int k=0;k*nums[index]+sum<=target;k++){
             if(k!=0) path.add(nums[index]);
             sum+=k*nums[index];
             dfs(nums,index+1);
             sum-=k*nums[index];//向上回溯的时候恢复现场
        }
        for(int k=1;k*nums[index]+sum<=target;k++){
            path.remove(path.size()-1);
        }

    }
    public List<List<Integer>> combinationSum(int[] nums, int target) {
        this.target=target; 
        dfs(nums,0);
        return ret; 
    }
}

六)组合总和(2) 

39. 组合总和 - 力扣(LeetCode)

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

class Solution {
    int sum=0;
    int target=0;
    List<List<Integer>> ret;
    List<Integer> path;
    boolean[] used;
    public List<List<Integer>> combinationSum2(int[] nums, int target) {
         this.ret=new ArrayList<>();
         this.path=new ArrayList<>();
         this.target=target;
         this.used=new boolean[nums.length];
         Arrays.sort(nums);
         dfs(nums,0);
         return ret;
    }
    public void dfs(int[] nums,int index){
        if(sum>target) return;
        if(sum==target){
            ret.add(new ArrayList<>(path));
            return;
        }
     for(int i=index;i<nums.length;i++){
         if(i!=index&&used[i-1]!=true&&nums[i]==nums[i-1]){
             continue;
         }
         path.add(nums[i]);
         sum+=nums[i];
         used[i]=true;
         dfs(nums,i+1);
         used[i]=false;
         sum-=nums[i]; 
        path.remove(path.size()-1);
     }
    }
}

其实本质上不使用check数组也是一样的,我们每一次从下一个位置开始进行枚举,就已经可以自动排除上一次曾经使用过的元素,自己一定要好好画决策树

class Solution {
List<List<Integer>> ret=new ArrayList<>();
List<Integer> path=new ArrayList<>();
int sum=0;
public void dfs(int[] nums,int target,int index){
    if(sum>target) return;
    if(sum==target){
        ret.add(new ArrayList<>(path));
        return;
    }
    if(path.size()==nums.length) return;
    for(int i=index;i<nums.length;i++){
       if(i!=index&&nums[i]==nums[i-1]){
            continue;
        }
       path.add(nums[i]);
       sum+=nums[i];
       dfs(nums,target,i+1);
       path.remove(path.size()-1);
       sum-=nums[i];
    }
}
public List<List<Integer>> combinationSum2(int[] nums, int target) {
    Arrays.sort(nums);
    dfs(nums,target,0);
    return ret;
}
}

如果我们最终发现时间超时,那么可能出现的bug就是没有正确的进行剪枝,导致一些冗余的情况进行计算了进来

七)路经总和

112. 路径总和 - 力扣(LeetCode)

解法1:找到二叉树的所有路径和,把他存放到一个list里面

相同子问题:跟定一个根节点,求以根节点为树的所有路径和

递归出口:当进行遍历到叶子结点的时候

dfs:向下一直找到叶子节点,如果遇到叶子节点,就把sum+root.val存放到最终结果中

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

class Solution {
    public int sum=0;
    List<Integer> list=new ArrayList<>();
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null) return false;
        dfs(root,0);
        return list.contains(targetSum);
    }
    public void dfs(TreeNode root,int sum){
       if(root.left==null&&root.right==null){
//与到叶子节点的时候才会进行计数,找到递归的出口
           list.add(sum+root.val);
           return;
       }
        if(root.left!=null) dfs(root.left,sum+root.val);
        if(root.right!=null) dfs(root.right,sum+root.val);
    }
}
解法2:使用回溯的方式,也是找到重复子问题:

1)观察我们要找的所有函数,我们可以查询出它的功能:询问是否从当前节点root到达叶子节点的路径,找到满足于路径和等于sum,假设从根节点到达当前节点的和是temp,那么我们只是需要找到是否从当前节点到达叶子节点,找到和等于sum-temp的叶子的路径,满足路径之和等于sum-temp

2)递归出口:当遍历到叶子结点的时候,判断sum-temp==true

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null) return false;
        if(root.left==null&&root.right==null){
            return root.val==targetSum;
        }
return hasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val);
    }
}

八)路经总和(2)

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

class Solution {
    List<Integer> path;
    List<List<Integer>> ret;
    int targetSum;
    int sum;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        this.path=new ArrayList<>();
        this.ret=new ArrayList<>();
        this.targetSum=targetSum;
        dfs(root);
     return ret;
    }
    public void dfs(TreeNode root){
        if(root==null) return;
        if(root.left==null&&root.right==null){
            path.add(root.val);
            sum+=root.val;
            if(sum==targetSum){
               ret.add(new ArrayList<>(path));
            }
            sum-=root.val;
            path.remove(path.size()-1);
//此时遍历到叶子结点的时候还是需要向上进行回溯操作
            return;
        }
    path.add(root.val);
    sum+=root.val;
    dfs(root.left);
//向上回溯,恢复现场
    sum-=root.val;
    path.remove(path.size()-1);
    path.add(root.val);
    sum+=root.val;
    dfs(root.right);
//向上回溯,恢复现场
    sum-=root.val;
    path.remove(path.size()-1);
    }
}

九)组合总和(3)

216. 组合总和 III - 力扣(LeetCode)文章来源地址https://www.toymoban.com/news/detail-627608.html

class Solution {
    List<Integer> path;
    List<List<Integer>> ret;
    int sum=0;
    int n=0;
    int target;
    public List<List<Integer>> combinationSum3(int n, int target) {
        this.path=new ArrayList<>();
        this.target=target;
        this.n=n;
        this.ret=new ArrayList<>();
        dfs(1);
        return ret;
    }
    public void dfs(int index){
        if(path.size()>n) return;
        if(sum==target&&path.size()==n){
            ret.add(new ArrayList<>(path));
            return;
        }
       for(int i=index;i<=9;i++){
           path.add(i);
           sum+=i;
           dfs(i+1);
           sum-=i;
           path.remove(path.size()-1);
       }
    }
}

到了这里,关于穷举&&深搜&&暴搜&&回溯&&剪枝(2)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索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

领红包