代码随想录算法训练营第二十一天| 回溯 216. 组合总和 III 17. 电话号码的字母组合
216. 组合总和 III
可以参考77.组合中关于选取数组的相关操作。
递归函数的返回值以及参数:一般为void类型
递归函数终止条件:path这个数组的大小如果达到k,说明我们找到了一个子集大小为k的组合了,然后当n为0的时候(找到数组值为n),终止,将结果导入res中
递归函数单层逻辑:回溯法的搜索过程就是一个树型结构的遍历过程,for循环用来横向遍历,递归的过程是纵向遍历。
class Solution {
public:vector<vector<int>>res;void backtracing(vector<int>path,int k,int n,int index){if(path.size()==k&&!n){res.push_back(path);return;}for(int i=index;i<=9;i++){path.push_back(i);n-=i;backtracing(path,k,n,i+1);n+=i;path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {vector<int>path;int index=1;backtracing(path,k,n,index);return res;}
};
剪枝操作

如果n为负了,就没有再继续减下去的必要了,可以提前回溯。
for(int i=index;i<=9-(k-path.size())+1;i++){path.push_back(i);n-=i;//提前回溯if(n<0){n+=i;path.pop_back();return;}backtracing(path,k,n,i+1);n+=i;path.pop_back();}
完整代码:
class Solution {
public:vector<vector<int>>res;void backtracing(vector<int>path,int k,int n,int index){if(path.size()==k&&!n){res.push_back(path);return;}for(int i=index;i<=9-(k-path.size())+1;i++){path.push_back(i);n-=i;if(n<0){n+=i;path.pop_back();return;}backtracing(path,k,n,i+1);n+=i;path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {vector<int>path;int index=1;backtracing(path,k,n,index);return res;}
};
17. 电话号码的字母组合
遇到回溯的题目,首先可以尝试画一下n叉树

确定回溯函数参数:首先需要一个字符串s来收集叶子节点的结果,然后用一个字符串数组result保存起来,这两个变量我依然定义为全局。再来看参数,参数指定是有题目中给的string digits,然后还要有一个参数就是int型的index。
确定终止条件:到达叶子结点是搜索,即stringg s的长度要与原先输入的长度相等
确定单层遍历逻辑:首先要取index指向的数字,并找到对应的字符集(手机键盘的字符集)。然后for循环来处理这个字符集。
class Solution {
public:const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};vector<string> res;string s;void backtracing(string digits,int index){if(index==digits.size()){res.push_back(s);return;}int num=digits[index]-'0';string letter=letterMap[num];for(int i=0;i<letter.size();i++){s.push_back(letter[i]);backtracing(digits,index+1);s.pop_back();}}vector<string> letterCombinations(string digits) {int index=0;if(!digits.size()) return res;backtracing(digits,index);return res;}
};
相关文章:
代码随想录算法训练营第二十一天| 回溯 216. 组合总和 III 17. 电话号码的字母组合
216. 组合总和 III 可以参考77.组合中关于选取数组的相关操作。 递归函数的返回值以及参数:一般为void类型 递归函数终止条件:path这个数组的大小如果达到k,说明我们找到了一个子集大小为k的组合了,然后当n为0的时候࿰…...
微服务架构最佳实践
我的新书《Android App开发入门与实战》已于2020年8月由人民邮电出版社出版,欢迎购买。点击进入详情 构建和管理微服务是一项艰巨的任务。这是因为微服务就像多个并行的整体应用程序,它们都必须处于同步通信和并发运行时间。因此,在设计和构建…...
国内首款支持苹果Find My芯片-伦茨科技ST17H6x
深圳市伦茨科技有限公司(以下简称“伦茨科技”)发布ST17H6x Soc平台。成为继Nordic之后全球第二家取得Apple Find My「查找」认证的芯片厂家,该平台提供可通过Apple Find My认证的Apple查找(Find My)功能集成解决方案。…...
linux 01 centos镜像下载,服务器,vmware模拟服务器
https://www.bilibili.com/video/BV1pz4y1D73n?p3&vd_source4ba64cb9b5f8c56f1545096dfddf8822 01.使用的版本 国内主要使用的版本是centos 02.centos镜像下载 这里的是centos7 一.阿里云官网地址:https://www.aliyun.com/ 二. -----【文档与社区】 —【…...
Linux安装RabbitMq明白纸(无图)
Linux安装RabbitMq步骤 安装环境Erlang和RabbitMQ版本对照安装包下载地址登录Linux服务器创建安装目录将之前下载的两个rpm文件上传到这个目录下,并解压安装Erlang安装完成后,查看Erlang版本安装socat(RabbitMq安装需要这个)解压并…...
Android - CrashHandler 全局异常捕获器
官网介绍如下:Thread.UncaughtExceptionHandler (Java Platform SE 8 ) 用于线程因未捕获异常而突然终止时调用的处理程序接口。当线程由于未捕获异常而即将终止时,Java虚拟机将使用thread . getuncaughtexceptionhandler()查询该线程的UncaughtExceptio…...
商品源数据如何采集,您知道吗?
如今,电子商务已经渗透到了人们生活的方方面面。2020年新冠肺炎突如其来,打乱了人们正常的生产生活秩序,给经济发展带来了极大的影响。抗击疫情过程中,为避免人员接触和聚集,以“无接触配送”为营销卖点的电子商务迅速…...
输入输出流、字符字节流、NIO
1、对输入输出流、字符字节流的学习,以之前做的批量下载功能为例 批量下载指的是,将多个文件打包到zip文件中,然后下载该zip文件。 1.1下载网络上的文件 代码参考如下: import java.io.*; import java.net.URL; import java.n…...
js中对数字,超大金额(千位符,小数点)格式化处理
前言 这个问题的灵感来自线上一个小bug,前两天刚看完同事写的代码,对数字类型处理的很好,之前一直都是用正则和toFixed(2)处理数字相关,后面发现使用numeral.js处理更完美。 对于下面这种数据的处理,你能想到几种方法…...
Android 打开热点2.4G系统重启解决
Android 打开热点2.4G系统重启解决 文章目录 Android 打开热点2.4G系统重启解决一、前言二、过程分析1、Android 设备开机后第一次打开热点2.4G系统重启2、日志分析3、设备重启原因 三、解决方法四、其他1、wifi/有线网 代理信息也可能导致系统重启2、Android13 热点默认5G频道…...
全链路压力测试有哪些主要作用
全链路压力测试是在软件开发和维护过程中不可或缺的一环,尤其在复杂系统和高并发场景下显得尤为重要。下面将详细介绍全链路压力测试的主要作用。 一、全链路压力测试概述 全链路压力测试是指对软件系统的全部组件(包括前端、后端、数据库、网络、中间件等)在高负载…...
【python基础教程】print输出函数和range()函数的正确使用方式
嗨喽,大家好呀~这里是爱看美女的茜茜呐 print()有多个参数,参数个数不固定。 有四个关键字参数(sep end file flush),这四个关键字参数都有默认值。 print作用是将objects的内容输出到file中,objects中的…...
LeetCode255.用队列实现栈
题目传送门:Leetcode255.用队列实现栈 请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。 实现 MyStack 类: void push(int x) 将元素 x 压…...
PHPStudy快速搭建网站并结合内网穿透远程访问本地站点
文章目录 [toc]使用工具1. 本地搭建web网站1.1 下载phpstudy后解压并安装1.2 打开默认站点,测试1.3 下载静态演示站点1.4 打开站点根目录1.5 复制演示站点到站网根目录1.6 在浏览器中,查看演示效果。 2. 将本地web网站发布到公网2.1 安装cpolar内网穿透2…...
AI嵌入式K210项目(1)-芯片开发板介绍
系列文章目录 在人工智能大潮滚滚而来的时代,作为一个从事嵌入式行业多年的程序猿倍感焦虑,有被替代的焦虑,也有跟不上新技术步伐的无奈,本系列文章将介绍一个从硬件设计到ai训练、最后到模型部署的完整案例;第一阶段…...
Blazor中使用impress.js
impress.js是什么? 你想在浏览器中做PPT吗?比如在做某些类似于PPT自动翻页,局部放大之类,炫酷无比。 在Blazor中,几经尝试,用以下方法可以实现。写文不易,请点赞、收藏、关注,并在转…...
ros2 ubuntu 20.04 安装 foxy
设置区域设置 确保您有一个支持UTF-8. 如果您处于最小环境(例如 docker 容器)中,则区域设置可能是最小的,例如POSIX. 我们使用以下设置进行测试。但是,如果您使用不同的 UTF-8 支持的区域设置,应该没问题。…...
Blazor 错误笔记
1. 运行时问题 Microsoft.NETCore.App.Runtime.Mono.browser-wasm Microsoft.NETCore.App.Runtime.Mono.browser-wasm 是一个 .NET Core 运行时的包,用于在浏览器中运行 .NET Core 应用程序。它是针对 WebAssembly 架构的 .NET Core 运行时,可以在浏览…...
【深度学习1对1指导】
...
XUbuntu22.04之快速复制绝对路径(二百零五)
简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏:多媒…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
LabVIEW双光子成像系统技术
双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制,展现出显著的技术优势: 深层组织穿透能力:适用于活体组织深度成像 高分辨率观测性能:满足微观结构的精细研究需求 低光毒性特点:减少对样本的损伤…...
关于easyexcel动态下拉选问题处理
前些日子突然碰到一个问题,说是客户的导入文件模版想支持部分导入内容的下拉选,于是我就找了easyexcel官网寻找解决方案,并没有找到合适的方案,没办法只能自己动手并分享出来,针对Java生成Excel下拉菜单时因选项过多导…...
永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器
一、原理介绍 传统滑模观测器采用如下结构: 传统SMO中LPF会带来相位延迟和幅值衰减,并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF),可以去除高次谐波,并且不用相位补偿就可以获得一个误差较小的转子位…...
