代码随想录算法训练营第22天-leetcode-回溯算法part01:
#回溯算法理论基础
能解决的问题:
- 组合问题:N个数里面按一定规则找出k个数的集合
- 切割问题:一个字符串按一定规则有几种切割方式
- 子集问题:一个N个数的集合里有多少符合条件的子集
- 排列问题:N个数按一定规则全排列,有几种排列方式
- 棋盘问题:N皇后,解数独等等
第77题. 组合
力扣题目链接(opens new window)
给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。
示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],
注意:
1、对于是递归回溯问题,用树图来考虑问题!+使用基本结构
同时,也要积极分析如何剪枝
2、路径类问题的标准套路:
在函数外开辟path 和 ans 一层空间 ans=(int**)malloc:一层空间,二层空间还没开辟
终止条件 if(一条路径完成了) 把path放入ans数组
先开辟ans的二层空间,ans【i】=(int*)malloc
放入path的过程需要用循环一个个放入,直接=path的话,后面会随path修改而修改
递归体:填充path
3、报错分析:
遇见heap堆错误,找malloc相关的;遇见stack栈报错,找函数内数组是否越界
4、returnsize 和 return column
*returnsize 在函数调用中无需&,且指向个数,而非下标
column的赋值过程:*column是正常数组,先为*column开辟空间,*column【第几个,<returnsize】=ans【第几个】有多少个二层元素
分析:
代码:
void bf(int *path,int n,int start,int k,int *pathlength,int **ans,int *returnSize){if(*pathlength == k-1){//路径类问题的标准输出ans[++(*returnSize)]=(int *)malloc(sizeof(int)*k);for (int i=0;i<k;i++){ans[*returnSize][i]=path[i];}return;}for(int i=start;i<=n-(k-*pathlength-2);i++){//遍历各个树//剪枝:如果后面全放进去,也达不到k个个数,那么就不考虑了path[++(*pathlength)]=i;bf(path,n,i+1,k,pathlength,ans,returnSize);(*pathlength)--;//回溯 步骤!!}
}int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {int **ans=(int **)malloc(sizeof(int *)*200001);*returnSize=-1;int pathlength=-1;//考虑路径,用到path,pathlengthint *path=(int *)malloc(sizeof(int )*k);bf(path,n,1, k, &pathlength,ans,returnSize);//returnsize不需要&(*returnSize)++;//returnsize指向数组的实际大小*returnColumnSizes=(int*)malloc(sizeof(int )*(*returnSize));//column的意义for(int i=0;i<(*returnSize);i++){(*returnColumnSizes)[i]=k;}return ans;
}
216.组合总和III
力扣题目链接(opens new window)
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
说明:
- 所有数字都是正整数。
- 解集不能包含重复的组合。
示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]
示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]
void bp(int **ans,int *size,int *path,int *p,int k,int n,int start,int sum){if(sum>n) return;//剪枝if(sum==n && *p==k){ans[*size]=(int *)malloc(sizeof(int)*k);for (int i=0;i<k;i++){ans[*size][i]=path[i];}(*size)++;return;//不要忘记写return}else if(*p==k){//另外一种终止情况return;}for(int i=start;i<=9;i++){path[(*p)++]=i;bp(ans, size, path, p, k, n, i+1, sum+i);//i+1,而不是start+1(*p)--;}
}int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes) {int **ans=(int **)malloc(sizeof(int *)*500);int size=0;int *path=(int *)malloc(sizeof(int)*k);int p=0;bp(ans, &size,path, &p, k, n, 1, 0);*returnSize=size;*returnColumnSizes=(int *)malloc(sizeof(int)*(size));for (int i=0;i<size;i++){(*returnColumnSizes)[i]=k;//要加括号}return ans;}
17.电话号码的字母组合
力扣题目链接(opens new window)
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
char phoneMap[11][5] = {"\0", "\0", "abc\0", "def\0", "ghi\0", "jkl\0", "mno\0", "pqrs\0", "tuv\0", "wxyz\0"};void bp(char**ans,int *size,char *path,int *p,int len,char* digits,int d){if(*p==len){ans[*size] =(char*)malloc(sizeof(char)*(len+1));for(int i=0;i<len;i++){ans[*size][i]=path[i];printf("%c",path[i]);} ans[*size][len]='\0';printf("\n");(*size)++;return;}int number= digits[d]-'0';char * nowd=phoneMap[number];int dlen=strlen(nowd);for(int i=0;i<dlen;i++){char new=nowd[i];path[(*p)++]=new;bp(ans, size, path,p, len, digits,d+1);(*p)--;}}char** letterCombinations(char* digits, int* returnSize) {int len=strlen(digits);char**ans=(char**)malloc(sizeof(char*)*pow(4,len));int size=0;if (len==0) {*returnSize=0;return ans;}char *path=(char*)malloc(sizeof(char)*(len+1));int p=0;bp(ans,&size, path, &p, len, digits, 0);*returnSize=size;return ans;}
相关文章:

代码随想录算法训练营第22天-leetcode-回溯算法part01:
#回溯算法理论基础 能解决的问题: 组合问题:N个数里面按一定规则找出k个数的集合切割问题:一个字符串按一定规则有几种切割方式子集问题:一个N个数的集合里有多少符合条件的子集排列问题:N个数按一定规则全排列&…...

MySql 触发器、存储器练习
一: 触发器 1、建立两个表:goods(商品表)、orders(订单表) 查看数据库:mysql> show databases; 使用数据库:mysql> use mydb16_trigger; 创建goods表: mysql> create table goods(gid char(8) not null primary key, …...

【Plotly-驯化】一文教您画出Plotly中动态可视化饼图:pie技巧
【Plotly-驯化】一文教您画出Plotly中动态可视化饼图:pie技巧 本次修炼方法请往下查看 🌈 欢迎莅临我的个人主页 👈这里是我工作、学习、实践 IT领域、真诚分享 踩坑集合,智慧小天地! 🎇 免费获取相关内…...

Mirror学习笔记(一) 简介
文章目录 一、常规学习:Mirror核心功能有服务器和主机 二、时间戳批处理时间戳 三、TCP和UDP四、CCU(同时在线人数)五、SyncDirection(同步方向)六、RTT(往返时间)七、Connection Quality(连接质量)八、Lag Compensati…...

终端pip安装包后,Pycharm却导入失败?新手别慌,3招搞定!
很多小伙伴在学习Python的过程中,都会遇到这种情况:明明在终端用pip安装好了需要的包,但在Pycharm中导入时却报错。难道是安装姿势不对? 例如在cmd中已经有了pandas,但是去pycharm中导入pandas显示没有 先别急着怀疑人生,这很可能是因为pip安装包的路径和Pycharm项目使用…...

Redis 与 Scrapy:无缝集成的分布式爬虫技术
1. 分布式爬虫的概念 分布式爬虫系统通过将任务分配给多个爬虫节点,利用集群的计算能力来提高数据抓取的效率。这种方式不仅可以提高爬取速度,还可以在单个节点发生故障时,通过其他节点继续完成任务,从而提高系统的稳定性和可靠性…...

大厂linux面试题攻略四之Linux网络服务(一)
一、Linux网络服务-SSH服务 1.哪些设置能够提升SSH远程管理的安全等级? ssh的登录验证方式 ssh的登录端口和监听设置: 配置文件: /etc/ssh/sshd_config #Port 22 #ssh服务默认监听端口 #ListenAddress 0.0.0.0 #ssh服务…...
【Pulling fs layer】Linux使用docker-compose的时候,一直Pulling fs layer
当Docker在拉取镜像时卡在“pulling fs layer”阶段,可以通过重启Docker服务来解决。 具体步骤如下: 首先,尝试重启Docker服务。可以通过运行以下命令来重启Docker服务: systemctl restart docker 这个命令会重启Docker服务…...

最新保姆级教程使用WildCard开通Claude3升级ChatGPT4.0(2024.8)
如何使用 WildCard 服务注册 Claude3 随着 Claude3 的震撼发布,最强 AI 模型的桂冠已不再由 GPT-4 独揽。Claude3 推出了三个备受瞩目的模型:Claude 3 Haiku、Claude 3 Sonnet 以及 Claude 3 Opus,每个模型都展现了卓越的性能与特色。其中&a…...

layui 乱入前端
功能包含 本实例代码为部分傻瓜框架,插入引用layui。因为样式必须保证跟系统一致,所以大部分功能都是自定义的。代码仅供需要用layui框架,但原项目又不是layui搭建的提供解题思路。代码较为通用 自定义分页功能自定义筛选列功能行内编辑下拉、…...

中国十大顶级哲学家,全球公认的伟大思想家颜廷利:人类为何拥有臀部
人类为何拥有臀部?若众生皆无此部位,又如何能寻得一处真正属于自己的“座位”?在博大精深的中国传统文化中,汉字“座”与“坐”均蕴含“土”字元素。在易经的智慧里,作为五行之一的“土”,象征着人类社会的…...

Threejs中导入GLTF模型克隆后合并
很多场景中会需要同一个模型很多次,但是如果多次加载同一个模型会占用很高的带宽,导致加载很慢,因此就需要使用clone,也就是加载一个模型后,其他需要使用的地方使用clone的方式复制出多个同样的模型,再改变…...

今日arXiv最热大模型论文:北京大学最新综述:视觉大模型中的漏洞与攻防对抗
近年来,视觉语言大模型(LVLM)在文本转图像、视觉问答等任务中大放异彩,背后离不开海量数据、强大算力和复杂参数的支撑。 但是!大模型看似庞大的身躯背后却有一颗脆弱的“心脏”,极易受到攻击。攻击者可以…...

为什么IDEA中使用@Autowired会被警告
我们在使用IDEA编码时,如果用到了Autowired注解注入bean,会发现IDEA会给代码标个波连线,鼠标移动上去,会发下idea提示:不推荐使用Filed injection,这是Spring的核心DI(Dendency Injection&#…...
uniapp使用cover-view,使用@click无效
最近要做直播详情页面,用的是第三方直播链接,需要在该页面上放两个按钮,点击按钮需要弹出相关商品及优惠券。类似于抖音直播页面。 第三方链接使用的是web-view进行展示。由于该组件优先级太高,正常的前端组件无法在该页面浮现展…...

Postman 接口测试工具简易使用指南
一、Postman是什么? 我通过kimi问了这样一个问题,它给我的回答是这样的: 它的回答也算比较中规中矩,简单的说postman实际上就是一款接口测试工具,同时它还可以编写对应的测试脚本以及自动生成对应的API文档,结合我的习惯来说&am…...

Move生态:从Aptos和Sui到Starcoin的崛起
区块链技术自诞生以来,已经经历了多个发展阶段和技术迭代。近年来,随着智能合约平台的不断演进,以Move语言为核心的生态系统逐渐崭露头角。Move语言以其安全性、灵活性和高效性吸引了大量开发者和项目方的关注。在Move生态中,Apto…...
MacOS DockerDesktop配置文件daemon.json的位置
如果因为通过可视化页面修改配置错误导致客户端启动不起来,可以去找对应的配置文件通过 vim 修改后重启客户端 cd ~/.docker/...

从光速常数的可变性看宇宙大爆炸的本质
基于先前关于光速本质的讨论,让我们从函数图像看看宇宙大爆炸到底是什么。 先前已经讨论过,在量子尺度上,长度的实际对应物是频率的差异,因为只有频率差异才能在这个尺度上区分相邻时空的两点,而两点之间“差异的大小”…...

敢不敢跟我一起搭建一个Agent!不写一行代码,10分钟搞出你的智能体!纯配置也能真正掌握AI最有潜力的技术?AI圈内人必备技能
说一千道一万,不如实地转一转。学了那么久的AI Agent的概念了,是时候该落地一个Agent看看自己的掌握程度了对不对,我们都理解大脑是自动节能的,但是知识的确需要倒逼自己一把才能真的掌握,不瞒大家说,笔者对…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

高考志愿填报管理系统---开发介绍
高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发,采用现代化的Web技术,为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## 📋 系统概述 ### 🎯 系统定…...
Java并发编程实战 Day 11:并发设计模式
【Java并发编程实战 Day 11】并发设计模式 开篇 这是"Java并发编程实战"系列的第11天,今天我们聚焦于并发设计模式。并发设计模式是解决多线程环境下常见问题的经典解决方案,它们不仅提供了优雅的设计思路,还能显著提升系统的性能…...