DFS

简介: -

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


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

回溯

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

与动态规划的区别

共同点

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

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

不同点

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

优化

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

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


练习

力扣

子集

基本思路

注意!!!

变量 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);

   }

}


全排列(无重复数据)

题目

分析

可能在这里回想为什么没有出现单体,例如[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;

           }

       }

   }

}

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

总结:

全排列2(有重复数据)

分析

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

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

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

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;

           }

       }

   }

}

组合总和

分析

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

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);

       }

   }

}

括号生成

分析

还是全排列的思想,但是有个限制:左右符号都等于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);

       }

   }

}

寻找重复的子树

/**

* 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;

   }

}

目录
相关文章
|
自然语言处理 搜索推荐 API
通义千问API:用4行代码对话大模型
本章将通过一个简单的例子,让你快速进入到通义千问大模型应用开发的世界。
通义千问API:用4行代码对话大模型
|
机器学习/深度学习 API 开发工具
通义千问API入门教程
本教程将带你从零开始,快速了解如何通过 API 使用通义千问大模型,并尝试使用大模型 API 开发一些简单的应用应用到工作中,提升效率。
|
并行计算
最新YOLOv8(2023年8月版本)安装配置!一条龙傻瓜式安装,遇到问题评论区提问
最近需要使用YOLOv8,百度了一下现在网上大多数教程都是比较早期的教程,很多文件已经大不相同,于是我根据官方readme文档,总结了一套安装方法,只需要按照本教程,复制每一段代码,按照教程配置好相应文件即可直接使用。
8541 2
|
安全 Linux 网络安全
【超详细】Linux系统修改SSH端口教程
在linux中,默认的SSH端口号为22,由于这是咱们都知道的端口号,一旦有入侵者进行端口扫描的时候扫描出22端口,就立马知道这是进行SSH登录的端口号,因而咱们需要修改默认的端口号。
12697 1
【超详细】Linux系统修改SSH端口教程
|
4月前
|
SQL 人工智能 自然语言处理
阿里云 AI 搜索开放平台新功能发布:新增GTE自部署模型
阿里云 AI搜索开放平台正式推出 GTE 多语言通用文本向量模型(iic/gte_sentence-embedding_multilingual-base)
336 4
|
SQL 人工智能 关系型数据库
SQL玩转多模态AI,轻松搞定图片+文本混合搜索
本文介绍了一种通过原生SQL实现多模态智能检索的破局思路,基于PolarDB创新融合AI智能引擎,解决传统AI检索系统数据迁移冗余和工具链割裂的问题。方案优势包括低门槛AI集成、灵活适配多场景、全链路数据安全及按需付费免运维。文章详细描述了部署资源、应用配置及方案验证步骤,并提供清理资源指南以避免额外费用。适合希望快速构建智能搜索应用的开发者参考实践。
|
Linux 网络安全 Python
linux centos上安装python3.11.x详细完整教程
这篇文章提供了在CentOS系统上安装Python 3.11.x版本的详细步骤,包括下载、解压、安装依赖、编译配置、解决常见错误以及版本验证。
8747 3
linux centos上安装python3.11.x详细完整教程
|
7月前
|
存储 Java
几种锁:偏向锁、轻量级锁、重量级锁、自旋锁
**锁机制简介:** Java中,锁分为偏向锁、轻量级锁和重量级锁。偏向锁适用于单一线程多次获取同一锁的情况,减少无竞争下的性能消耗;轻量级锁在多线程竞争时通过自旋避免阻塞,提升效率;重量级锁则是在自旋超时或多个线程竞争时,将其他线程阻塞以防止CPU空转,但性能较低。锁的升级路径为:偏向锁 → 轻量级锁 → 重量级锁,且不可降级。偏向锁默认开启,可通过JVM参数调整或关闭。
305 13
几种锁:偏向锁、轻量级锁、重量级锁、自旋锁
|
9月前
「Mac畅玩鸿蒙与硬件46」UI互动应用篇23 - 自定义天气预报组件
本篇将带你实现一个自定义天气预报组件。用户可以通过选择不同城市来获取相应的天气信息,页面会显示当前城市的天气图标、温度及天气描述。这一功能适合用于动态展示天气信息的小型应用。
392 38
「Mac畅玩鸿蒙与硬件46」UI互动应用篇23 - 自定义天气预报组件
|
消息中间件 NoSQL Java
Redis系列学习文章分享---第六篇(Redis实战篇--Redis分布式锁+实现思路+误删问题+原子性+lua脚本+Redisson功能介绍+可重入锁+WatchDog机制+multiLock)
Redis系列学习文章分享---第六篇(Redis实战篇--Redis分布式锁+实现思路+误删问题+原子性+lua脚本+Redisson功能介绍+可重入锁+WatchDog机制+multiLock)
462 0