代码随想录算法训练营第二十一天| 回溯 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工程师进阶系列【原创干货持续更新中……】🚀 优质专栏:多媒…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
