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

代码随想录算法训练营第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:

#回溯算法理论基础 能解决的问题&#xff1a; 组合问题&#xff1a;N个数里面按一定规则找出k个数的集合切割问题&#xff1a;一个字符串按一定规则有几种切割方式子集问题&#xff1a;一个N个数的集合里有多少符合条件的子集排列问题&#xff1a;N个数按一定规则全排列&…...

MySql 触发器、存储器练习

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

【Plotly-驯化】一文教您画出Plotly中动态可视化饼图:pie技巧

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

Mirror学习笔记(一) 简介

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

终端pip安装包后,Pycharm却导入失败?新手别慌,3招搞定!

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

Redis 与 Scrapy:无缝集成的分布式爬虫技术

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

大厂linux面试题攻略四之Linux网络服务(一)

一、Linux网络服务-SSH服务 1.哪些设置能够提升SSH远程管理的安全等级? ssh的登录验证方式 ssh的登录端口和监听设置&#xff1a; 配置文件: /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”阶段&#xff0c;可以通过重启Docker服务来解决。 具体步骤如下&#xff1a; 首先&#xff0c;尝试重启Docker服务。可以通过运行以下命令来重启Docker服务&#xff1a; systemctl restart docker 这个命令会重启Docker服务…...

最新保姆级教程使用WildCard开通Claude3升级ChatGPT4.0(2024.8)

如何使用 WildCard 服务注册 Claude3 随着 Claude3 的震撼发布&#xff0c;最强 AI 模型的桂冠已不再由 GPT-4 独揽。Claude3 推出了三个备受瞩目的模型&#xff1a;Claude 3 Haiku、Claude 3 Sonnet 以及 Claude 3 Opus&#xff0c;每个模型都展现了卓越的性能与特色。其中&a…...

layui 乱入前端

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

中国十大顶级哲学家,全球公认的伟大思想家颜廷利:人类为何拥有臀部

人类为何拥有臀部&#xff1f;若众生皆无此部位&#xff0c;又如何能寻得一处真正属于自己的“座位”&#xff1f;在博大精深的中国传统文化中&#xff0c;汉字“座”与“坐”均蕴含“土”字元素。在易经的智慧里&#xff0c;作为五行之一的“土”&#xff0c;象征着人类社会的…...

Threejs中导入GLTF模型克隆后合并

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

今日arXiv最热大模型论文:北京大学最新综述:视觉大模型中的漏洞与攻防对抗

近年来&#xff0c;视觉语言大模型&#xff08;LVLM&#xff09;在文本转图像、视觉问答等任务中大放异彩&#xff0c;背后离不开海量数据、强大算力和复杂参数的支撑。 但是&#xff01;大模型看似庞大的身躯背后却有一颗脆弱的“心脏”&#xff0c;极易受到攻击。攻击者可以…...

为什么IDEA中使用@Autowired会被警告

我们在使用IDEA编码时&#xff0c;如果用到了Autowired注解注入bean&#xff0c;会发现IDEA会给代码标个波连线&#xff0c;鼠标移动上去&#xff0c;会发下idea提示&#xff1a;不推荐使用Filed injection&#xff0c;这是Spring的核心DI&#xff08;Dendency Injection&#…...

uniapp使用cover-view,使用@click无效

最近要做直播详情页面&#xff0c;用的是第三方直播链接&#xff0c;需要在该页面上放两个按钮&#xff0c;点击按钮需要弹出相关商品及优惠券。类似于抖音直播页面。 第三方链接使用的是web-view进行展示。由于该组件优先级太高&#xff0c;正常的前端组件无法在该页面浮现展…...

Postman 接口测试工具简易使用指南

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

Move生态:从Aptos和Sui到Starcoin的崛起

区块链技术自诞生以来&#xff0c;已经经历了多个发展阶段和技术迭代。近年来&#xff0c;随着智能合约平台的不断演进&#xff0c;以Move语言为核心的生态系统逐渐崭露头角。Move语言以其安全性、灵活性和高效性吸引了大量开发者和项目方的关注。在Move生态中&#xff0c;Apto…...

MacOS DockerDesktop配置文件daemon.json的位置

如果因为通过可视化页面修改配置错误导致客户端启动不起来&#xff0c;可以去找对应的配置文件通过 vim 修改后重启客户端 cd ~/.docker/...

从光速常数的可变性看宇宙大爆炸的本质

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

敢不敢跟我一起搭建一个Agent!不写一行代码,10分钟搞出你的智能体!纯配置也能真正掌握AI最有潜力的技术?AI圈内人必备技能

说一千道一万&#xff0c;不如实地转一转。学了那么久的AI Agent的概念了&#xff0c;是时候该落地一个Agent看看自己的掌握程度了对不对&#xff0c;我们都理解大脑是自动节能的&#xff0c;但是知识的确需要倒逼自己一把才能真的掌握&#xff0c;不瞒大家说&#xff0c;笔者对…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

【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哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 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毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...

Java并发编程实战 Day 11:并发设计模式

【Java并发编程实战 Day 11】并发设计模式 开篇 这是"Java并发编程实战"系列的第11天&#xff0c;今天我们聚焦于并发设计模式。并发设计模式是解决多线程环境下常见问题的经典解决方案&#xff0c;它们不仅提供了优雅的设计思路&#xff0c;还能显著提升系统的性能…...