当前位置: 首页 > news >正文

DFS算法专题(二)——穷举vs暴搜vs深搜vs回溯vs剪枝【OF决策树】

目录

1、决策树

2、算法实战应用【leetcode】

2.1 题一:全排列

2.2.1 算法原理

2.2.2 算法代码

2.2 题二:子集

2.2.1 算法原理【策略一】

2.2.2 算法代码【策略一】

2.2.3  算法原理【策略二,推荐】

2.2.4 算法代码【策略二,推荐】

2.3 题三:找出所有子集的异或总和再求和

2.3.1 算法原理

2.3.2 算法代码【解法一】(不推荐)

 2.3.3 算法代码【解法二】(推荐)

 2.4 题四:全排列 II

2.4.1 算法原理

2.4.2 算法代码


1、决策树

决策树是一种树形结构的监督学习算法,广泛应用于分类任务和回归任务中。它通过递归地将数据集分割成更小的子集,最终形成一个树形模型,用于预测新数据的输出。

决策树是一种树形结构,其中每个内部节点表示一个属性上的测试,每个分支代表一个测试输出,每个叶节点代表一种类别。

决策树是一种十分常用的分类方法。它是一种监督学习,所谓监督学习就是给定一堆样本,每个样本都有一组属性和一个类别,这些类别是事先确定的,那么通过学习得到一个分类器,这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。

面对上难度的DFS算法题,我们首先要做的就是画出决策树。

注意:画出的决策树越详细越好!!!

2、算法实战应用【leetcode】

2.1 题一:全排列

. - 力扣(LeetCode)

2.2.1 算法原理

  1. 画出决策树,记住:决策树越详细越好!!!
  2. 设置全局变量(全局变量的设置因题而异),本题设置二维数组ret为返回值,记录全部的全排列;数组path记录路径;布尔类型的check数组实现剪枝操作
  3. 对于递归函数,我们仍然要站在宏观角度,聚焦于某一层要做的事来设计
  4. DFS算法,不可避免的就是回溯、剪枝与函数出口等细节问题的考虑
  5. 对于本题回溯的设计,在dfs完下一层,回到当前层后,再进行恢复现场的操作(删除下一层在path中的数据),注意:本题需要对path和check均进行回溯操作
  6. 对于本题剪枝的设计,通过布尔数组的判断,判断数组中数据可否放进路径path中
  7. 对于本题递归函数的出口,将path中存放数据的数量和nums数组长度相比较,若相等,则添加到ret中。

2.2.2 算法代码

class Solution {List<List<Integer>> ret;List<Integer> path;boolean[] check;public List<List<Integer>> permute(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();check = new boolean[nums.length];dfs(nums);return ret;}public void dfs(int[] nums) {//函数出口if(path.size() == nums.length) {ret.add(new ArrayList<>(path));return;}for(int i = 0; i < nums.length; i++) {if(!check[i]) {path.add(nums[i]);check[i] = true;dfs(nums);//将下一层中的相关数据删除 -> 回溯 -> 恢复现场 -> 1.path 2.check//add新数据时,递归仍然在本层中,add的是本层i位置处的新数据,//dfs完后,i仍然为本层add时的数据的下标,//此时回溯要将path和check恢复现场path.remove(path.size() - 1);check[i] = false;}}}
}

2.2 题二:子集

. - 力扣(LeetCode)

2.2.1 算法原理【策略一】

  1. 画决策树
  2. 设置全局变量 : ①:List<List<Integer>> ret;//返回值     ②:List<Integer> path;//记录路径
  3. 设计函数头:void dfs(nums, pos);//pos为下一次进入path中元素的下标
  4. 设计函数体:①:选:path += nums[pos]; dfs(nums,pos+1);②:不选:dfs(nums,pos+1);
  5. 考虑函数出口:pos == nums.length;将path添加进ret中,return;
  6. 处理细节问题:①:回溯 -> 恢复现场:path.remove(pathsize()-1); ②:剪枝:无

2.2.2 算法代码【策略一】

class Solution {List<List<Integer>> ret;List<Integer> path;public List<List<Integer>> subsets(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();dfs(nums, 0);return ret;}public void dfs(int[] nums, int pos) {//函数出口if(pos == nums.length) {ret.add(new ArrayList<>(path));return;}//选path.add(nums[pos]);dfs(nums, pos + 1);//回溯 -> 恢复现场path.remove(path.size() - 1);//不选(不做任何操作即可)dfs(nums, pos + 1);}
}

2.2.3  算法原理【策略二,推荐】

思想 

  • 分三个支线,每个节点就是一个子集,所以每刚进入递归函数时,就把path添加进ret中,pos依然为下一个要添加进path中的元素的下标。叶子节点即为函数出口

 步骤:

  1. 画决策树
  2. 设计代码 ①全局变量 ret/path ②函数头 void dfs(nums, pos); ③函数体 1.ret.add(path);2.依次枚举该节点后的元素 ④函数出口  无
  3. 细节问题 ①回溯 -> 恢复现场:path.remove(path,size()-1) ②剪枝 -> 无

2.2.4 算法代码【策略二,推荐】

class Solution {List<List<Integer>> ret;List<Integer> path;public List<List<Integer>> subsets(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();dfs(nums, 0);return ret;}public void dfs(int[] nums, int pos) {ret.add(new ArrayList<>(path));//从pos位置开始向后枚举for(int i = pos; i < nums.length; i++) {//依次枚举,下标为ipath.add(nums[i]);//从当前元素后面的元素中选dfs(nums, i + 1);//回溯 -> 恢复现场path.remove(path.size() - 1);}}
}

2.3 题三:找出所有子集的异或总和再求和

. - 力扣(LeetCode)

2.3.1 算法原理

本题与上一题解题思想如出一辙,

解法一:直接cv上一题的代码,再将每组子集相异或再求和。(不推荐)

解法二:将path设置为每个子集的异或值(策越二,每个节点都是一个子集),再创建一个全局变量sum求和即可,回溯时直接利用异或消消乐的特性恢复现场即可。

解法二的时间效率更加优秀,建议大家使用解法二解题。

2.3.2 算法代码【解法一】(不推荐)

class Solution {List<List<Integer>> total;List<Integer> path;public int subsetXORSum(int[] nums) {total = new ArrayList<>();path = new ArrayList<>();List<Integer> sum = new ArrayList<>();dfs(nums, 0);for(int i = 0; i < total.size(); i++) {int ret = 0;for(int j = 0; j < total.get(i).size(); j++) {ret ^= (total.get(i).isEmpty() ? 0 : total.get(i).get(j));}sum.add(ret);}int val = 0;for(int x : sum) val += x;return val;}public void dfs(int[] nums, int pos) {total.add(new ArrayList<>(path));for(int i = pos; i < nums.length; i++) {path.add(nums[i]);dfs(nums, i + 1);path.remove(path.size() - 1);}}
}

 2.3.3 算法代码【解法二】(推荐)

class Solution {int path;//每个子集所有元素的异或值int sum;public int subsetXORSum(int[] nums) {path = 0;sum = 0;dfs(nums, 0);return sum;}public void dfs(int[] nums, int pos) {sum += path;for(int i = pos; i < nums.length; i++) {path ^= nums[i];dfs(nums, i + 1);//回溯 -> 恢复现场 -> 异或:消消乐path ^= nums[i];}}
}

 2.4 题四:全排列 II

. - 力扣(LeetCode)

2.4.1 算法原理

本题整体框架与上文题一全排列相同,回溯函数出口函数体等设计这里不再赘述。

由于出现重复的元素,故本题算法需要添加更多的剪枝操作。

在数组有序的情况下(有序时相同的元素才会相邻),我们可以这样来设计剪枝:

  1. 剪枝:

①:同一个元素只能出现一次 --> boolean[] check
②:在一个节点的分支中,相同数值的元素只能选择一次

  1. 筛选节点:

符合条件的节点:
check[i]==flase && (i==0 || nums[i-1] != nums[i] || check[i-1]==true)

2.4.2 算法代码

class Solution {List<List<Integer>> ret;List<Integer> path;boolean[] check;//同一个数据,只能出现一次public List<List<Integer>> permuteUnique(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();check = new boolean[nums.length];//数据有序的情况下,保证重复的元素是相邻的Arrays.sort(nums);dfs(nums);return ret;}public void dfs(int[] nums) {if(path.size() == nums.length) {ret.add(new ArrayList<>(path));return;}for(int i = 0; i < nums.length; i++) {//剪枝 -> 筛选出符合条件的分支//同一个数据只能出现一次 && 一个节点上,相同数值的元素只能选择一次if(!check[i] && (i == 0 || nums[i - 1] != nums[i] || check[i - 1])) {path.add(nums[i]);check[i] = true;dfs(nums);//回溯 -> 恢复现场path.remove(path.size() - 1);check[i] = false;}}}
}

END 

相关文章:

DFS算法专题(二)——穷举vs暴搜vs深搜vs回溯vs剪枝【OF决策树】

目录 1、决策树 2、算法实战应用【leetcode】 2.1 题一&#xff1a;全排列 2.2.1 算法原理 2.2.2 算法代码 2.2 题二&#xff1a;子集 2.2.1 算法原理【策略一】 2.2.2 算法代码【策略一】 2.2.3 算法原理【策略二&#xff0c;推荐】 2.2.4 算法代码【策略二&#x…...

Spring Security 快速开始

<dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-security</artifactId></dependency> 一、认证 1、从数据中读数据完成认证 Service public class MyUserDetailsService implements UserDeta…...

Lua5.3 参考手册

《Lua 5.3 参考手册》是对 Lua 5.3 版本语言的官方定义。这份手册详细描述了 Lua 语言的语法、语义以及标准库和 C API。它是由巴西里约热内卢 Pontifical Catholic 大学的 PUC-Rio 团队开发的&#xff0c;并且是一个自由软件&#xff0c;广泛应用于世界各地的产品和项目中【9†…...

Centos如何配置阿里云的yum仓库作为yum源?

背景 Centos在国内访问官方yum源慢&#xff0c;可以用国内的yum源&#xff0c;本文以阿里云yum源为例说明。 快速命令 sudo mv /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-Base.repo.bak sudo wget -O /etc/yum.repos.d/CentOS-Base.repo http://mirrors.a…...

力扣139-单词拆分(Java详细题解)

题目链接&#xff1a;139. 单词拆分 - 力扣&#xff08;LeetCode&#xff09; 前情提要&#xff1a; 因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。 最近刚学完背包&#xff0c;所以现在的题解都是以背包问题为基础再来写的。 如果大家不懂背包问题的话&#…...

CSS —— display属性

用于指定一个元素在页面中的显示方式 HTML中标签元素大体被分为三种类型&#xff1a;块元素、行内元素和行内块元素 块元素 &#xff1a;block 1.独占一行 2.水平方向&#xff0c;占满它父元素的可用空间&#xff08;宽度是父级的100%&#xff09; 3.垂直方向&#xff0c;占据的…...

BTC ETF资金流入暴涨400%,市场下一步将如何发展?

近期&#xff0c;BTC现货ETF&#xff08;交易所交易基金&#xff09;市场出现了显著的资金流入&#xff0c;尤其是在9月10日&#xff0c;BTC ETF吸引了近1.17亿美元的资金流入&#xff0c;相较于前一天的3729万美元&#xff0c;暴涨了400%。这种现象引发了市场广泛关注&#xf…...

视频监控管理平台LntonAIServer视频智能分析抖动检测算法应用场景

在视频监控系统中&#xff0c;视频画面的稳定性对于确保监控效果至关重要。抖动现象是指视频画面中存在不稳定或频繁晃动的情况&#xff0c;这可能会影响视频的清晰度和可读性。LntonAIServer通过引入抖动检测功能&#xff0c;帮助用户及时发现并解决视频流中的抖动问题&#x…...

初识php库管理工具composer的体验【爽】使用phpword模板功能替换里面的字符串文本

需求&#xff1a; 做了一个租赁的项目&#xff0c;里面要求签署个人授权协议&#xff0c;里面要填写姓名&#xff0c;手机号&#xff0c;身份证号&#xff0c;签署日期等参数&#xff0c;格式如下图 格式&#xff1a; 如上图&#xff0c;word中的字符串模板变量使用${varname…...

每日一问:C++ 如何实现继承、封装和多态

每日一问&#xff1a;C 如何实现继承、封装和多态 C 是一门面向对象编程语言&#xff0c;通过继承、封装和多态这三个核心特性实现了对复杂系统的高效管理和扩展。继承让代码重用性得以提升&#xff0c;封装保护数据的完整性&#xff0c;而多态通过不同的接口实现了灵活性。本文…...

STM32常用数据采集滤波算法

例如&#xff0c;STM32进行滤波处理时&#xff0c;主要目的是处理数据采集过程中可能产生的噪声和尖刺信号。这些噪声可能来自电源干扰、传感器自身的不稳定性或其他外部因素。 1.一阶互补滤波 方法&#xff1a;取a0~1,本次滤波结果&#xff08;1-a&#xff09;本次采样值a上…...

二分系列(二分查找)9/12

一、分情况讨论 1.左闭右闭:[left,right] 因为是左闭右闭&#xff0c;所以left和right都能直接取到。 #这里将>放到一起&#xff0c;当nums[mid]>target的时候&#xff0c; 要更新右边界&#xff0c;rightmid-1,这样就把一些相同的情况也切出去了 可以理解为找的第一个…...

如何通过可视化大屏,助力智慧城市的“城市微脑”建设?

在智慧城市的宏伟蓝图中&#xff0c;常常面临着一个关键挑战&#xff1a;如何确保这些理念和技术能够真正地惠及城市的每一个角落&#xff0c;每一个产业&#xff0c;以及每一位市民。问题的核心在于城市的具体应用场景&#xff0c;无论是横向的社区、园区、镇街、学校、酒店、…...

何时空仓库

某仓库现存货物 s 箱&#xff0c;每天上午出货 m 箱、下午进货 n 箱&#xff0c;若s≥m>n≥0&#xff0c;则第 k 天将会出现空仓的情况。请你帮仓库管理员编写程序&#xff0c;输入s、m 和 n&#xff0c;计算并输出 k。 输入格式 s,m,n (s≥m>n≥0) 输出格式 k 输入样例…...

美创获评CNVD年度原创漏洞发现贡献单位!

9月10日&#xff0c;第21届中国网络安全年会暨网络安全协同治理分论坛在广州成功举办。会上&#xff0c;美创科技首次获评“CNVD年度原创漏洞发现贡献单位”。 美创科技依托第59号安全实验室&#xff0c;专注数据安全技术和攻防研究。凭借深厚的技术积累与优势&#xff0c;被遴…...

Spring 循环依赖原理及解决方案

一、什么是循环依赖 循环依赖指的是一个实例或多个实例存在相互依赖的关系&#xff08;类之间循环嵌套引用&#xff09;。 举例&#xff1a; Component public class AService {// A中注入了BAutowiredprivate BService bService; }Component public class BService {// B中也…...

【数据结构与算法 | 灵神题单 | 插入链表篇】力扣2807, LCR 029, 147

1. 力扣2807&#xff1a;在链表中插入最大公约数 1.1 题目&#xff1a; 你一个链表的头 head &#xff0c;每个结点包含一个整数值。 在相邻结点之间&#xff0c;请你插入一个新的结点&#xff0c;结点值为这两个相邻结点值的 最大公约数 。 请你返回插入之后的链表。 两个…...

瑞芯微rv1126 Linux 系统,修改系统时区,包有效方法

在 Linux 系统中,修改时区的步骤通常包括创建符号链接到正确的时区文件,并确保相关的配置文件已正确更新。然而,某些系统可能有额外的步骤或需要修改其他配置文件来使更改生效。以下是一些步骤。 1. 创建符号链接 ln -sf /usr/share/zoneinfo/Asia/Hong_Kong /etc/localti…...

系统架构设计师:数据库设计

简简单单 Online zuozuo: 简简单单 Online zuozuo 简简单单 Online zuozuo 简简单单 Online zuozuo 简简单单 Online zuozuo :本心、输入输出、结果 简简单单 Online zuozuo : 文章目录 系统架构设计师:数据库设计前言数据库基础概念数据模型三要素数据库的三级模型和两级…...

代码随想录刷题day31丨56. 合并区间,738.单调递增的数字,总结

代码随想录刷题day31丨56. 合并区间&#xff0c;738.单调递增的数字&#xff0c;总结 1.题目 1.1合并区间 题目链接&#xff1a;56. 合并区间 - 力扣&#xff08;LeetCode&#xff09; 视频讲解&#xff1a;贪心算法&#xff0c;合并区间有细节&#xff01;LeetCode&#x…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...