当前位置: 首页 > 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…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

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

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

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

客户案例 | 短视频点播企业海外视频加速与成本优化:MediaPackage+Cloudfront 技术重构实践

01技术背景与业务挑战 某短视频点播企业深耕国内用户市场&#xff0c;但其后台应用系统部署于东南亚印尼 IDC 机房。 随着业务规模扩大&#xff0c;传统架构已较难满足当前企业发展的需求&#xff0c;企业面临着三重挑战&#xff1a; ① 业务&#xff1a;国内用户访问海外服…...