子集和全排列(深度优先遍历)问题
欢迎访问杀马特主页:小小杀马特主页呀!
目录
前言:
例题一·全排列:
1.题目介绍:
2.思路汇总:
3.代码解答:
例题二·子集:
题目叙述:
解法一:
1.思路汇总:
2.代码解答:
解法二:
1.思路汇总:
2.代码解答:
文末小总结:
前言:
本篇采用两道例题来讲解利用枚举元素的方法使用决策树通过递归以及穿插回溯来解答类似此类问题的系列模版操作(涉及全局变量以及引用传参使用需要回溯问题与具体什么时候使用等)。
当我们使用全局变量大都就要手动的回溯了,因为它回归到上一层自己不会改变,这里既可以选择全局变量又可以选择引用传参,但是比如一个递归函数需要使用多个变量,这时候引用传参就麻烦了,故需要我们使用全局变量了,因此视情况而定(本篇我们都使用的是全局变量)。
例题一·全排列:
1.题目介绍:

欢迎大家来挑战:leetcode原题链接: . - 力扣(LeetCode)
2.思路汇总:
画出决策树,然后令dfs函数能帮我们完成此元素位置(从其上到末的path都放入ret)然后对于这个数组就是要遍历它了,由于我们要定义的path是全局遍历故
要考虑回溯(复原操作):这里就是我们每次往后递归,不能出现前面的元素,故这里开一个bool类型数组记录一下
(一开始是false,变成true就是已经出现了,故不进行操作继续循环)
终止条件:当path满了(等于nums的size)就返回就行了。
思路:从下标0开始遍历数组,遍历到一个就放入path,记录状态,然后继续下面递归,依次重复,
最后肯定会path等于size然后就放入ret,然后回溯:在上一层完成删除path的back即恢复现场的操作,每一次完成一条路线就往回溯,最后归到第一次for循环到退出。
决策图解:

3.代码解答:
class Solution {
public:vector<vector<int>> ret;vector<int> path;bool check[7]={false};//如果换成vector的bool类型只能用原数组指针区间初始化void dfs(vector<int>& nums){if(path.size()==nums.size()){ret.push_back(path);//终止条件return;}for(int i=0;i<nums.size();i++){if(check[i]==false){//使用后该状态防止重复使用path.push_back(nums[i]);check[i]=true;dfs(nums);//回溯(恢复现场):path.pop_back();check[i]=false;}}}vector<vector<int>> permute(vector<int>& nums) {dfs(nums);return ret;}};
例题二·子集:
本题采取两种解法解答,一种是叶子节点放入ret,另一种就是每当递归到一层,这一层的path就是要存入ret的结果。
题目叙述:

欢迎大家来挑战:leetcode原题链接:. - 力扣(LeetCode)
解法一:
1.思路汇总:
思路:枚举元素:分为选i位置的数和不选两条路径,然后往下递归,最后决策树相当于叶子节点的数就是我们要推进ret的,这里可以假设dfs递归函数可以帮我们完成从传入
的pos位置一直走到叶子位置的所有分支路径最后的到叶子节点的path都放入ret,然后在第一次分别传入它的左支和右支就可以了。
细节:注意传入的pos的位置以及回溯的时候path的变化

2.代码解答:
class Solution {
public:vector<vector<int>> ret;vector<int> path;
void dfs(vector<int>& nums,int pos){if(pos==nums.size()){ret.push_back(path);path.pop_back();//回溯return;}//可分为左支不走,右支走://走pos位置的元素(右支):path.push_back(nums[pos]);dfs(nums,pos+1);//不走pos位置的元素(左支):dfs(nums,pos+1);}vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;}
解法二:
1.思路汇总:
思路:我们遍历数组放入path,并且当递归到下一层遍历的时候就是当前位置的下一个开始,所以循环的第一个是pos位置,结合每次下一层递归结束回到上一层都会把下一层的
path里面加入的nums[i]删除即回溯,保证了每次每当我们进入一次递归第一个就是子集。
细节:1·为什么ret添加不在for里面:这样的话最后一次递归完成后无法添加最后一次的结果。
2·为什么每次递归函数传参是i+1不是pos+1呢:这样的话就会导致递归回来的时候走for里的i++的时候再次传入pos+1,又会进行刚才的递归操作了,不符合预期。

2.代码解答:
void dfs(vector<int>& nums,int pos){ret.push_back(path);for(int i=pos;i<nums.size();i++){path.push_back(nums[i]);dfs(nums,i+1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;}
文末小总结:
像这种类型的dfs思路就是首先根据题意采取穷举等方法画出决策树,然后根据规则转化成递归代码:终止条件,递归操作,回溯,剪枝的判断,其次就是合理应用全局变量等
相关文章:
子集和全排列(深度优先遍历)问题
欢迎访问杀马特主页:小小杀马特主页呀! 目录 前言: 例题一全排列: 1.题目介绍: 2.思路汇总: 3.代码解答: 例题二子集: 题目叙述: 解法一: 1.思路汇总…...
判断检测框是否在感兴趣区域(ROI)内
判断检测框是否在感兴趣区域(ROI)内 在计算机视觉和图像处理中,我们经常需要确定一个矩形检测框是否位于一个特定的感兴趣区域(Region of Interest, ROI)内。这个ROI可以是一个多边形,而检测框则是一个矩形…...
正点原子阿尔法ARM开发板-IMX6ULL(九)——关于SecureCRT连接板子上的ubuntu
文章目录 一、拨码器二、SecureCRT 一、拨码器 emmm,也是好久没学IMX6ULL了,也是忘了拨码器决定了主板的启动方式 一种是直接从TF卡中读取文件(注意这里是通过imdownload软件编译好了之后,通过指令放入TF卡) 一种是现在这种用串口…...
微信支付Java+uniapp微信小程序
JS: request.post(/vip/pay, {//这是自己写的java支付接口id: this.vipInfo.id,payWay: wechat-mini}).then((res) > {let success (res2) > {//前端的支付成功回调函数this.$refs.popup.close();// 支付成功刷新当前页面setTimeout(() > {this.doGetVipI…...
【NOIP提高组】加分二叉树
【NOIP提高组】加分二叉树 💐The Begin💐点点关注,收藏不迷路💐 设一个n个节点的二叉树tree的中序遍历为(l,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整…...
HarmonyOS 相对布局(RelativeContainer)
1. HarmonyOS 相对布局(RelativeContainer) 文档中心:https://developer.huawei.com/consumer/cn/doc/harmonyos-guides-V5/arkts-layout-development-relative-layout-V5 RelativeContainer为采用相对布局的容器,支持容器内部的子元素设…...
webpack5搭建react脚手架详细步骤
1. 初始化项目 首先,创建一个新目录并初始化项目: bash mkdir create-react cd create-react pnpm init --y git init 这里使用pnpm作为包管理工具,因为它在处理依赖和速度上表现更好。 2. 安装React和TypeScript 安装React和React-DOM…...
速盾:高防cdn怎么拦截恶意ip?
高防CDN(Content Delivery Network)是一种用于防御网络攻击和提供高可用性的服务。它通过分发网络流量,将用户的请求导向最近的服务器,从而提高网站的加载速度和稳定性。然而,不可避免地,有些恶意IP地址会试…...
太阳能面板分割系统:训练自动化
太阳能面板分割系统源码&数据集分享 [yolov8-seg-EfficientHead&yolov8-seg-vanillanet等50全套改进创新点发刊_一键训练教程_Web前端展示] 1.研究背景与意义 项目参考ILSVRC ImageNet Large Scale Visual Recognition Challenge 项目来源AAAI Globa…...
C++笔记---位图
1. 位图的概念 位图(Bitmap)是一种基于位操作的数据结构,用于表示一组元素的集合信息。它通常是一个仅包含0和1的数组,每个元素对应一个二进制位,若该元素存在,则对应的位为1;若不存在ÿ…...
ABC370
## A - Raise Both Hands (模拟) 题意:输入l,r,如果l1r0输出yes,l0r1输出no,否则输出Invalid 代码: #include<bits/stdc.h> using namespace std; typedef long long ll; vo…...
C语言[求x的y次方]
C语言——求x的y次方 这段 C 代码的目的是从用户输入获取两个整数 x 和 y ,然后计算 x 的 y 次幂(不过这里有个小错误,实际计算的是 x 的 (y - 1) 次幂,后面会详细说),最后输出结果。 代码如下: #include…...
JavaScript part2
一.前言 前面我们讲了一下js的基础语法,但是这些还是远远不够的,我们要想操作标签,实现一个动态且好看的页面,就得学会BOM和DOM,这些都是浏览器和页面的,这样我们才能实现一个好看的页面 二.BOM对象 BOM…...
HarmonyOS开发 - 本地持久化之实现LocalStorage实例
用户首选项为应用提供Key-Value键值型的数据处理能力,支持应用持久化轻量级数据,并对其修改和查询。数据存储形式为键值对,键的类型为字符串型,值的存储数据类型包括数字型、字符型、布尔型以及这3种类型的数组类型。 说明&#x…...
【C++打怪之路Lv12】-- 模板进阶
#1024程序员节|征文# 🌈 个人主页:白子寰 🔥 分类专栏:重生之我在学Linux,C打怪之路,python从入门到精通,数据结构,C语言,C语言题集👈 希望得到您…...
第23周Java主流框架入门-SpringMVC 2.RESTful开发风格
课程笔记:RESTful 开发风格 课程介绍 本节课程介绍 RESTful 开发风格,以及如何在 Spring MVC 中应用这种开发模式。传统 MVC 开发通过 Servlet、JSP 和 Java Bean 实现前后端交互,而 RESTful 开发提供了一种新的理念,更适合现代…...
QT枚举类型转字符串和使用QDebug<<重载输出私有枚举类型
一 将QT自带的枚举类型转换为QString 需要的头文件: #include <QMetaObject> #include <QMetaEnum> 测试代码 const QMetaObject *metaObject &QImage::staticMetaObject;QMetaEnum metaEnum metaObject->enumerator(metaObject->indexOf…...
手机柔性屏全贴合视觉应用
在高科技日新月异的今天,手机柔性显示屏作为智能手机市场的新宠,以其独特的可弯曲、轻薄及高耐用性特性引领着行业潮流。然而,在利用贴合机加工这些先进显示屏的过程中,仍面临着诸多技术挑战。其中,高精度对位、应力控…...
《Python游戏编程入门》注-第3章3
《Python游戏编程入门》的“3.2.4 Mad Lib”中介绍了一个名为“Mad Lib”游戏的编写方法。 1 游戏玩法 “Mad Lib”游戏由玩家根据提示输入一些信息,例如男人姓名、女人姓名、喜欢的食物以及太空船的名字等。游戏根据玩家输入的信息编写出一个故事,如图…...
Netty-TCP服务端粘包、拆包问题(两种格式)
前言 最近公司搞了个小业务,需要使用TCP协议,我这边负责服务端。客户端是某个设备,客户端传参格式、包头包尾等都是固定的,不可改变,而且还有个蓝牙传感器,透传数据到这个设备,然后通过这个设备…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

