当前位置: 首页 > 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面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

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"…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

算法250609 高精度

加法 #include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; char input1[205]; char input2[205]; int main(){while(scanf("%s%s",input1,input2)!EOF){int a[205]…...