开发者社区> 游客wiepw7jj4edse> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

DFS

简介: -
+关注继续查看

深度优先搜索是递归实现的,是要搜索整个二叉树的,在这个搜索的基础上,再加点回溯/剪枝的操作就是这一类排列组合的题了,是这个关系


  • 空间复杂度为O(h)O(h),对空间复杂度高的考虑DFS
  • 不具备最短性

回溯

现实无法回到过去,就在程序回到过去吧!

与动态规划的区别

共同点

  • 用于求解多阶段决策问题。多阶段决策问题即:

  • 求解一个问题分为很多步骤(阶段);
  • 每一个步骤(阶段)可以有多种选择。

不同点

  • 动态规划只需要求我们评估最优解是多少,最优解对应的具体解是什么并不要求。因此很适合应用于评估一个方案的效果;
  • 回溯算法可以搜索得到所有的方案(当然包括最优解),但是本质上它是一种遍历算法,时间复杂度很高。

优化

由于回溯算法的时间复杂度很高,因此在遍历的时候,如果能够提前知道这一条分支不能搜索到满意的结果,就可以提前结束,这一步操作称为 剪枝

排序主要的作用,让程序在深搜的过程中尽量排除掉不能搜索到结果的分支,以节约时间。在回溯搜索这种时间复杂度很大的算法中,先排序再剪枝有些时候是有必要的。


练习

力扣

子集

基本思路

image

image

注意!!!

变量 t 所指向的列表 在深度优先遍历的过程中只有一份 ,深度优先遍历完成以后,回到了根结点,成为空列表。

在 Java 中,参数传递是 值传递,对象类型变量在传参的过程中,复制的是变量的地址。这些地址被添加到 res 变量,但实际上指向的是同一块内存地址,因此我们会看到 66 个空的列表对象。

解决的方法很简单,在 ans.add(new ArrayList<Integer>(t)); 这里做一次拷贝即可。

class Solution {

    List<Integer> t = new ArrayList<Integer>();

    List<List<Integer>> ans = new ArrayList<List<Integer>>();


    public List<List<Integer>> subsets(int[] nums) {

        dfs(0, nums);

        return ans;

    }


    public void dfs(int cur, int[] nums) {

        if (cur == nums.length) {

            ans.add(new ArrayList<Integer>(t));

            return;

        }

        t.add(nums[cur]);

        dfs(cur + 1, nums);

        t.remove(t.size() - 1);

        dfs(cur + 1, nums);

    }

}


全排列(无重复数据)

题目

image

分析

image

可能在这里回想为什么没有出现单体,例如[1]或者[1,2]这种,这里的判断条件和子集那道题不一样,

子集那题的计数,可能在nums.length-1时执行了一次,所以出现只有一个数的数组,执行几次便有几个

class Solution {

    public List<List<Integer>> permute(int[] nums) {

        List<Integer> List = new ArrayList<>();

        List<List<Integer>> res = new ArrayList<>();

        boolean[] st = new boolean[nums.length];

        if(nums.length==0)return res;

        DFS(nums,res,List,st);

        return res;

    }

    public void DFS(int[] nums, List<List<Integer>> res, List<Integer> List, boolean[] st){

        if(List.size() == nums.length){

            res.add(new ArrayList<>(List));

            return;

        }

        for(int i = 0; i < nums.length; i ++){

            if(!st[i]){

                List.add(nums[i]);

                st[i]=true;

                DFS(nums,res,List,st);

                List.remove(List.size()-1);

                st[i]=false;

            }

        }

    }

}

基础不牢,多练练这个,注意代码规范

总结:

image

全排列2(有重复数据)

image

分析

拿到题目,发现重复元素,便想到重复必有影响,例如两个相同元素交换可能又是一组数据,想到了剪枝

image

因为全排列,所以数据不够的不会被选中,我们只需要让重复的数据无法继续即可

  • 如果这个数和前一个数相同且前一个数还没有用过,continue
  • 比如11'2可以,1'12不行,因为1'在1前面使用,1还未使用

image

class Solution {

    public List<List<Integer>> permuteUnique(int[] nums) {

        List<Integer> list = new ArrayList<Integer>();

        List<List<Integer>> res = new ArrayList<List<Integer>>();

        boolean[] st = new boolean[nums.length];

        Arrays.sort(nums);//要去重,故先排序

        DFS(nums,list,res,st);

        return res;

    }

    public void DFS(int[] nums, List<Integer> list, List<List<Integer>> res, boolean[] st){

        if(list.size()==nums.length){

            //注意不要写成List<Integer>

            res.add(new ArrayList<>(list));

            return;

        }

        for(int i = 0; i < nums.length; i ++){

            if(i>0&&nums[i]==nums[i-1]&&!st[i-1])continue;

            if(!st[i]){

                list.add(nums[i]);

                st[i]=true;

                DFS(nums,list,res,st);

                list.remove(list.size()-1);

                st[i]=false;

            }

        }

    }

}

组合总和

image

分析

还是全排列,然后将符合的加入,能优化就是剪枝,关键点排序,主要的作用,让程序在深搜的过程中尽量排除掉不能搜索到结果的分支

DFS一般就那几个参数

如果不是全局变量,DFS(答案合集,单个答案,条件,目标,计数)

第一种成员

class Solution {

    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        List<Integer> path = new ArrayList<>();

        

        Arrays.sort(candidates);

        backtrack(path,candidates,target,0,0);

        return res;

    }

    public void backtrack(List<Integer> path,int[] candidates, int target, int sum, int begin){

        if(sum==target){

            res.add(new ArrayList<>(path));

            return;

        }

        for(int i = begin; i < candidates.length; i ++){

            int rs = sum + candidates[i];

            if(sum<=target){

                path.add(candidates[i]);

                backtrack(path,candidates,target,rs,i);

                path.remove(path.size() - 1);


            }else{

                break;

            }

        }

    }

}

第二种非成员(推荐)-方法本类就是适用于各种情况

class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        List<List<Integer>> ans = new ArrayList<List<Integer>>();

        List<Integer> combine = new ArrayList<Integer>();

        dfs(candidates, target, ans, combine, 0);

        return ans;

    }


    public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {

        if (idx == candidates.length) {

            return;

        }

        if (target == 0) {

            ans.add(new ArrayList<Integer>(combine));

            return;

        }

        // 直接跳过

        dfs(candidates, target, ans, combine, idx + 1);

        // 选择当前数

        if (target - candidates[idx] >= 0) {

            combine.add(candidates[idx]);

            dfs(candidates, target - candidates[idx], ans, combine, idx);

            combine.remove(combine.size() - 1);

        }

    }

}

括号生成

image

分析

还是全排列的思想,但是有个限制:左右符号都等于n时才算数据,可以采用剪枝(左边大于右边时结束,因为是有效的,必须保证左括号先有)

class Solution {

    public List<String> generateParenthesis(int n) {

        List<String> res = new ArrayList<>();

        DFS("",0,0,res,n);

        return res;

    }

    public void DFS(String curStr,int left, int right, List<String> res, int n){

        if(left==n && right==n){

            res.add(curStr);

            return;

        }

        if(left<right)return;

        if(left<n){

            DFS(curStr+"(",left+1,right,res,n);

        }

        if(right<n){

            DFS(curStr+")",left,right+1,res,n);

        }

    }

}

寻找重复的子树

image

/**

* Definition for a binary tree node.

* public class TreeNode {

*     int val;

*     TreeNode left;

*     TreeNode right;

*     TreeNode() {}

*     TreeNode(int val) { this.val = val; }

*     TreeNode(int val, TreeNode left, TreeNode right) {

*         this.val = val;

*         this.left = left;

*         this.right = right;

*     }

* }

*/

class Solution {

    Map<String,TreeNode> coll = new HashMap<String,TreeNode>();

    Set<TreeNode> res = new HashSet<TreeNode>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {

        dfs(root);

        return new ArrayList<>(res);

    }

    public String dfs(TreeNode root){

        if(root==null)return "";

        StringBuilder sb = new StringBuilder();

        sb.append(root.val).append("(");

        sb.append(dfs(root.left)).append(")(");

        sb.append(dfs(root.right)).append(")");

        String serial = sb.toString();

        if(coll.containsKey(serial)){

            res.add(coll.get(serial));

        }else{

            coll.put(serial,root);

        }

        return serial;

    }

}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
DFS(一)
.是求路径条数,还是路径本身(或动作序列)? DFS最常见的三个问题,求可行解的总数,求一个可行解,求所有可行解。 (a)如果是路径条数,则不需要存储路径
33 0
DO447管理任务执行--控制提权
DO447管理任务执行--控制提权
51 0
DDNS
一、DDNS简介 DNS,域名系统,是因特网的一项服务,它作为将域名和IP地址相互映射的一个分布式数据库,能够使人们更方便的访问互联网。 DDNS,动态域名系统,是域名系统(DNS)中的一种自动更新名称服务器内容的技术。
7518 0
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载