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

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...