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

回溯法(一)——全排列 全组合 子集问题

全排列问题

  • 数字序列 [ l , r ] [l,r] [l,r]​区间内元素的全排列问题
全排列问题递归树
extern int ans[],l,r,num;//num:方案数
extern bool flag[];
void dfs(int cl){//cl:current left,即为当前递归轮的首元素if(cl == r + 1){//数组已越界,本轮递归结束for(int i=l;i<=r;i++) cout<<ans[i];//从区间头开始扫描并输出cout<<endl;num++;return;}for(int i=l;i<=r;i++){//if(!flag[i]){//剪枝:不允许重复选择已被选择的元素flag[i]=1,ans[cl]=i;dfs(cl + 1);flag[i]=0;//回溯}}
}
全排列问题重复排列剪枝
  • 数组索引 [ l , r ] [l,r] [l,r]​区间内元素的全排列问题

思路:

  1. 让当前的首元素(索引为 c l cl cl)不同,分割成 r r r轮,(首元素相同的称为1轮,共 r r r轮)
    方法:首元素和其之后每个元素交换 (for控制 r r r轮广度)
  2. 每轮中第 [ l + 1 , r ] [l+1,r] [l+1,r]的元素分割出来小区间,令 c l = l + 1 cl=l+1 cl=l+1(对应dfs递归传参),重复步骤1。
    方法:递归控制
extern int a[],l,r,num;//num:方案数
void dfs(int cl){//cl:current left,即为当前递归轮的首元素if(cl == r + 1){//数组已越界,本轮递归结束for(int i = l; i <= r; i++)//从用户输入区间头开始遍历输出cout << a[i];cout << endl;num++;return;}for(int i = cl; i <= r; i++){//从本轮递归区间头开始扫描 i=cl是因为数组本身也算是一种排列方案swap(a[cl], a[i]);//本轮递归区间首元素与其之后每个元素都互换dfs(cl + 1);swap(a[cl], a[i]);//回溯}
}

全组合问题

  • [ l , r ] [l,r] [l,r]区间内组合问题
extern int n, l, r,ans[n];
void dfs(int k, int last) {//k:当前已选元素个数 last:上一轮递归中选择的元素值if (k == n + 1) {//k已越界,输出答案for (int i = 0; i < n; i++) cout<<ans[i]<<' ';cout<<endl;return;}for (int i = last + 1; i <= r; i++) {//从last+1开始是为了选择不会与上一轮递归重复ans[k - 1] = i;dfs(k + 1, i);}
}
int main() {//...dfs(1, l - 1); // 从l-1开始,确保l能被选中//...
}

子集问题

相关文章:

回溯法(一)——全排列 全组合 子集问题

全排列问题 数字序列 [ l , r ] [l,r] [l,r]​区间内元素的全排列问题 extern int ans[],l,r,num;//num&#xff1a;方案数 extern bool flag[]; void dfs(int cl){//cl:current left&#xff0c;即为当前递归轮的首元素if(cl r 1){//数组已越界&#xff0c;本轮递归结束for…...

【Pt】马灯贴图绘制过程 04-玻璃脏迹

目录 效果 步骤 一、透明玻璃 二、烟熏痕迹 三、粗糙 四、浮尘 效果 步骤 一、透明玻璃 1. 打开纹理集设置&#xff0c;着色器链接选择“新的着色器链接” 在着色器设置中可以看到此时名称为“Main shader &#xff08;Copy&#xff09;” 这里修改名称为“玻璃” 在…...

Rust 程序设计语言学习——枚举模式匹配

枚举&#xff08;enumerations&#xff09;&#xff0c;也被称作 enums。match 允许我们将一个值与一系列的模式相比较&#xff0c;并根据相匹配的模式执行相应代码。 1 枚举的定义 假设我们要跨省出行&#xff0c;有多种交通工具供选择。常用的交通工具有飞机、火车、汽车和轮…...

正则表达式(1)

文章目录 专栏导读1、match2、匹配目标3、通用匹配4、常用匹配规则表格 专栏导读 ✍ 作者简介&#xff1a;i阿极&#xff0c;CSDN 数据分析领域优质创作者&#xff0c;专注于分享python数据分析领域知识。 ✍ 本文录入于《python网络爬虫实战教学》&#xff0c;本专栏针对大学生…...

nginx + keepalived 搭建教程

1.安装依赖 yum install -y keepalived systemctl start keepalived systemctl enable keepalived 2.配置 a. keepalived.conf配置 global_defs {router_id nginx_server2 # 机器标识(backup节点为nfs_server2) }vrrp_script chk { script "/etc/keepalived/check_po…...

React事件和原生事件的执行顺序

在 React 中&#xff0c;事件处理分为两种类型&#xff1a;React 合成事件&#xff08;Synthetic Event&#xff09;和原生 DOM 事件&#xff08;Native DOM Event&#xff09;。它们的执行顺序略有不同。 React 合成事件 React 合成事件的执行顺序&#xff1a; React 合成事件…...

为什么在计算查询Q和键K的矩阵乘法时需要转置键矩阵K。示例说明q11,k11代表什么。线性变换矩阵 W_q 用于生成查询,W_k 用于生成键怎么获取的。

目录 为什么在计算查询Q和键K的矩阵乘法时需要转置键矩阵K。 示例说明q11,k11代表什么。...

剑指Offer题目笔记27(动态规划单序列问题)

面试题89&#xff1a; 问题&#xff1a; ​ 输入一个数组表示某条街道上的一排房屋内财产的数量。相邻两栋房屋不能同时被盗&#xff0c;问小偷能偷取到的最多财物。 解决方案一&#xff08;带缓存的递归&#xff09;&#xff1a; 解决方案&#xff1a; 由于有报警系统&…...

撸代码时,有哪些习惯一定要坚持?

我从2011年开始做单片机开发&#xff0c;一直保持以下撸代码的习惯。 1.做好代码版本管理 有些人&#xff0c;喜欢一个程序干到底&#xff0c;直到实现全部的产品功能&#xff0c;我以前做51单片机的项目就是这样。 如果功能比较多的产品&#xff0c;我不建议这样做&#xff0…...

【leetcode面试经典150题】17.罗马数字转整数(C++)

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主&#xff0c;题解使用C语言。&#xff08;若有使用其他语言的同学也可了解题解思路&#xff0c;本质上语法内容一致&…...

前后端开发之——文章分类管理

原文地址&#xff1a;前后端开发之——文章分类管理 - Pleasure的博客 下面是正文内容&#xff1a; 前言 上回书说到 文章管理系统之添加文章分类。就是通过点击“新建文章分类”按钮从而在服务端数据库中增加一个文章分类。 对于文章分类这个对象&#xff0c;增删改查属于配…...

第12届蓝桥杯省赛 ---- C/C++ C组

文章目录 1. ASC2. 空间3. 卡片4. 相乘5. 路径6.时间显示7.最少砝码8. 杨辉三角形9. 左孩子右兄弟 第12届蓝桥杯省赛&#xff0c;C/C C组真题&#xff0c;第10题不是很清楚&#xff0c;题解不敢乱放&#x1f601;&#x1f601;&#x1f601; 1. ASC 额。。。。 #include <i…...

IVS模型解释

核心思路 【Implied volatility surface predictability: The case of commodity markets】 半参数化模型&#xff1a;利用各种参数(或者因子)对隐含波动率进行降维&#xff08;静态参数化因子模型&#xff09;&#xff0c;对参数化因子的时间序列进行间接的建模 基于非对称…...

通用开发技能系列:Git

云原生学习路线导航页&#xff08;持续更新中&#xff09; 本文是 通用开发技能系列 文章&#xff0c;主要对编程通用技能Git进行学习 1.为什么使用版本控制系统 版本控制系统可以解决的问题 代码备份很重要版本控制很重要协同工作很重要责任追溯很重要 常见的版本控制系统 Gi…...

最新怎么订阅OnlyFans上喜欢的博主,详细教程

大家好&#xff0c;本文教大家如何用虚拟信用卡在 Onlyfans 订阅&#xff0c;链接在浏览器打开地址https://bewildcard.com/i/GPT310&#xff0c;虚拟卡开好之后&#xff0c;用支付宝充值就可以进行订阅OnlyFans平台的博主了。 什么是OnlyFans&#xff1f; OnlyFans 是一个提…...

Mysql故障和优化

一、MySQL故障 二、MySQL优化 1.硬件优化&#xff1a; 2.数据库设计与规划 1.提前估计数据量&#xff0c;使用什么存储引擎 2.数据库服务器专机专用&#xff0c;避免额外的服务可能导致的性能下降和不稳定性 3.增加多台服务器&#xff0c;以达到稳定、高效的效果。主从同步、…...

Windows系统C盘空间优化进阶:磁盘清理与Docker日志管理

Windows系统C盘空间优化进阶&#xff1a;磁盘清理与Docker日志管理 文章目录 Windows系统C盘空间优化进阶&#xff1a;磁盘清理与Docker日志管理磁盘清理工具 使用“运行”命令访问磁盘清理利用存储感知自动管理空间清理WinSxS文件夹结合手动清理策略 小结删除临时文件总结&…...

14届蓝桥杯 C/C++ B组 T7 子串简写 (字符串)

采用存储目标字符下标的方法&#xff0c;此题的想法比较新奇&#xff0c;故予以记录。 存好下标之后&#xff0c;可以先定位好启始的字符&#xff0c;然后去搜结尾字符符合长度k并且最靠近启始字符的下标&#xff0c;找到之后可以直接取到这个下标之后的所有下标&#xff0c;因…...

Android 系统大致启动流程

Android启动流程大体为&#xff1a;BootRom -> BootLoader -> Kernel -> Init -> Zygote -> SystemServer ->Launcher 1、Loader层 1.1、Boot ROM 电源按下&#xff0c;引导芯片代码开始从预定义的地方&#xff08;固化在ROM&#xff09;开始执行&#xff0…...

【Web】2024红明谷CTF初赛个人wp(2/4)

目录 ezphp playground 时间原因只打了2个小时&#xff0c;出了2道&#xff0c;简单记录一下 ezphp 参考文章 PHP filter chains: file read from error-based oracle https://github.com/synacktiv/php_filter_chains_oracle_exploit 用上面的脚本爆出部分源码&#xff…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...