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

代码随想录算法训练营第二十一天| 回溯 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.组合中关于选取数组的相关操作。 递归函数的返回值以及参数&#xff1a;一般为void类型 递归函数终止条件&#xff1a;path这个数组的大小如果达到k&#xff0c;说明我们找到了一个子集大小为k的组合了&#xff0c;然后当n为0的时候&#xff0…...

微服务架构最佳实践

我的新书《Android App开发入门与实战》已于2020年8月由人民邮电出版社出版&#xff0c;欢迎购买。点击进入详情 构建和管理微服务是一项艰巨的任务。这是因为微服务就像多个并行的整体应用程序&#xff0c;它们都必须处于同步通信和并发运行时间。因此&#xff0c;在设计和构建…...

国内首款支持苹果Find My芯片-伦茨科技ST17H6x

深圳市伦茨科技有限公司&#xff08;以下简称“伦茨科技”&#xff09;发布ST17H6x Soc平台。成为继Nordic之后全球第二家取得Apple Find My「查找」认证的芯片厂家&#xff0c;该平台提供可通过Apple Find My认证的Apple查找&#xff08;Find My&#xff09;功能集成解决方案。…...

linux 01 centos镜像下载,服务器,vmware模拟服务器

https://www.bilibili.com/video/BV1pz4y1D73n?p3&vd_source4ba64cb9b5f8c56f1545096dfddf8822 01.使用的版本 国内主要使用的版本是centos 02.centos镜像下载 这里的是centos7 一.阿里云官网地址&#xff1a;https://www.aliyun.com/ 二. -----【文档与社区】 —【…...

Linux安装RabbitMq明白纸(无图)

Linux安装RabbitMq步骤 安装环境Erlang和RabbitMQ版本对照安装包下载地址登录Linux服务器创建安装目录将之前下载的两个rpm文件上传到这个目录下&#xff0c;并解压安装Erlang安装完成后&#xff0c;查看Erlang版本安装socat&#xff08;RabbitMq安装需要这个&#xff09;解压并…...

Android - CrashHandler 全局异常捕获器

官网介绍如下&#xff1a;Thread.UncaughtExceptionHandler (Java Platform SE 8 ) 用于线程因未捕获异常而突然终止时调用的处理程序接口。当线程由于未捕获异常而即将终止时&#xff0c;Java虚拟机将使用thread . getuncaughtexceptionhandler()查询该线程的UncaughtExceptio…...

商品源数据如何采集,您知道吗?

如今&#xff0c;电子商务已经渗透到了人们生活的方方面面。2020年新冠肺炎突如其来&#xff0c;打乱了人们正常的生产生活秩序&#xff0c;给经济发展带来了极大的影响。抗击疫情过程中&#xff0c;为避免人员接触和聚集&#xff0c;以“无接触配送”为营销卖点的电子商务迅速…...

输入输出流、字符字节流、NIO

1、对输入输出流、字符字节流的学习&#xff0c;以之前做的批量下载功能为例 批量下载指的是&#xff0c;将多个文件打包到zip文件中&#xff0c;然后下载该zip文件。 1.1下载网络上的文件 代码参考如下&#xff1a; import java.io.*; import java.net.URL; import java.n…...

js中对数字,超大金额(千位符,小数点)格式化处理

前言 这个问题的灵感来自线上一个小bug&#xff0c;前两天刚看完同事写的代码&#xff0c;对数字类型处理的很好&#xff0c;之前一直都是用正则和toFixed(2)处理数字相关&#xff0c;后面发现使用numeral.js处理更完美。 对于下面这种数据的处理&#xff0c;你能想到几种方法…...

Android 打开热点2.4G系统重启解决

Android 打开热点2.4G系统重启解决 文章目录 Android 打开热点2.4G系统重启解决一、前言二、过程分析1、Android 设备开机后第一次打开热点2.4G系统重启2、日志分析3、设备重启原因 三、解决方法四、其他1、wifi/有线网 代理信息也可能导致系统重启2、Android13 热点默认5G频道…...

全链路压力测试有哪些主要作用

全链路压力测试是在软件开发和维护过程中不可或缺的一环&#xff0c;尤其在复杂系统和高并发场景下显得尤为重要。下面将详细介绍全链路压力测试的主要作用。 一、全链路压力测试概述 全链路压力测试是指对软件系统的全部组件(包括前端、后端、数据库、网络、中间件等)在高负载…...

【python基础教程】print输出函数和range()函数的正确使用方式

嗨喽&#xff0c;大家好呀~这里是爱看美女的茜茜呐 print()有多个参数&#xff0c;参数个数不固定。 有四个关键字参数&#xff08;sep end file flush&#xff09;&#xff0c;这四个关键字参数都有默认值。 print作用是将objects的内容输出到file中&#xff0c;objects中的…...

LeetCode255.用队列实现栈

题目传送门&#xff1a;Leetcode255.用队列实现栈 请你仅使用两个队列实现一个后入先出&#xff08;LIFO&#xff09;的栈&#xff0c;并支持普通栈的全部四种操作&#xff08;push、top、pop 和 empty&#xff09;。 实现 MyStack 类&#xff1a; void push(int x) 将元素 x 压…...

PHPStudy快速搭建网站并结合内网穿透远程访问本地站点

文章目录 [toc]使用工具1. 本地搭建web网站1.1 下载phpstudy后解压并安装1.2 打开默认站点&#xff0c;测试1.3 下载静态演示站点1.4 打开站点根目录1.5 复制演示站点到站网根目录1.6 在浏览器中&#xff0c;查看演示效果。 2. 将本地web网站发布到公网2.1 安装cpolar内网穿透2…...

AI嵌入式K210项目(1)-芯片开发板介绍

系列文章目录 在人工智能大潮滚滚而来的时代&#xff0c;作为一个从事嵌入式行业多年的程序猿倍感焦虑&#xff0c;有被替代的焦虑&#xff0c;也有跟不上新技术步伐的无奈&#xff0c;本系列文章将介绍一个从硬件设计到ai训练、最后到模型部署的完整案例&#xff1b;第一阶段…...

Blazor中使用impress.js

impress.js是什么&#xff1f; 你想在浏览器中做PPT吗&#xff1f;比如在做某些类似于PPT自动翻页&#xff0c;局部放大之类&#xff0c;炫酷无比。 在Blazor中&#xff0c;几经尝试&#xff0c;用以下方法可以实现。写文不易&#xff0c;请点赞、收藏、关注&#xff0c;并在转…...

ros2 ubuntu 20.04 安装 foxy

设置区域设置 确保您有一个支持UTF-8. 如果您处于最小环境&#xff08;例如 docker 容器&#xff09;中&#xff0c;则区域设置可能是最小的&#xff0c;例如POSIX. 我们使用以下设置进行测试。但是&#xff0c;如果您使用不同的 UTF-8 支持的区域设置&#xff0c;应该没问题。…...

Blazor 错误笔记

1. 运行时问题 Microsoft.NETCore.App.Runtime.Mono.browser-wasm Microsoft.NETCore.App.Runtime.Mono.browser-wasm 是一个 .NET Core 运行时的包&#xff0c;用于在浏览器中运行 .NET Core 应用程序。它是针对 WebAssembly 架构的 .NET Core 运行时&#xff0c;可以在浏览…...

【深度学习1对1指导】

...

XUbuntu22.04之快速复制绝对路径(二百零五)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景

Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知&#xff0c;帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量&#xff0c;能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度&#xff0c;还为机器人、医疗设备和制造业的智…...