003. 电话号码的字母组合——回溯算法

news/2024/3/29 1:03:36/文章来源:https://blog.csdn.net/qq_70280303/article/details/128080454

1.题目链接:

17. 电话号码的字母组合

2.解题思路:

2.1.题目要求:

给定一个仅包含数字 2-9 的字符串 digits ,返回所有它能表示的字母组合。

数字和字母的关系:

例子:

输入:"23"

输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]

2.2.思路:

制作成n叉树,比如下图,输入"23",遍历完 2 的字母然后又遍历 3的字母。

2.3.回溯三部曲:

先用二维数组映射数字和字母的关系

const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9
};

 

2.3.1.确定回溯函数参数

 首先需要一个字符串s来收集叶子节点的结果,然后用一个字符串数组result保存起来,这两个定义为全局变量,可以显的参数简洁一点。

函数的参数写题目传进来的数字字符串 digits ,以及int型的index(代表遍历的层数)

index用于终止条件,作用是统计数字数量,用于终止条件(下面解释)

vector<string> result;
string s;
void backtracking(const string& digits, int index)

 

2.3.2.确定终止条件

终止条件就是当 输入的数字个数(digits.size) 等于 index 遍历的层数后,把字符串 s 搜集到的结果,传入结果集 result。

if (index == digits.size()) {result.push_back(s);return;
}

 

2.3.3.确定单层遍历逻辑

先将 字符串digits 里的"数字"转成int类型的数字,因为题目给的数字实际上是字符串...需要先进行转化,

用这个数字取上面定义的数字和字母的映射,取出数字对应的字母集,用于for循环(for循环里在按顺序取出字母进行配对)

int digit = digits[index] - '0';        // 将index指向的数字转为int
string letters = letterMap[digit];      // 取数字对应的字符集

 后面就是for循环了,遍历的结果输入储存字符串 s 里面,用于在终止条件触发的时候,输入结果集,同时记得要回溯。

for (int i = 0; i < letters.size(); i++) {s.push_back(letters[i]);            // 处理backtracking(digits, index + 1);    // 递归,注意index+1,一下层要处理下一个数字了s.pop_back();                       // 回溯
}

组合一下:

int digit = digits[index] - '0';        // 将index指向的数字转为int
string letters = letterMap[digit];      // 取数字对应的字符集
for (int i = 0; i < letters.size(); i++) {s.push_back(letters[i]);            // 处理backtracking(digits, index + 1);    // 递归,注意index+1,一下层要处理下一个数字了s.pop_back();                       // 回溯
}

 

2.4.总代码:

// 版本一
class Solution {
private:const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};
public:vector<string> result;string s;void backtracking(const string& digits, int index) {if (index == digits.size()) {result.push_back(s);return;}int digit = digits[index] - '0';        // 将index指向的数字转为intstring letters = letterMap[digit];      // 取数字对应的字符集for (int i = 0; i < letters.size(); i++) {s.push_back(letters[i]);            // 处理backtracking(digits, index + 1);    // 递归,注意index+1,一下层要处理下一个数字了s.pop_back();                       // 回溯}}vector<string> letterCombinations(string digits) {s.clear();result.clear();if (digits.size() == 0) {return result;}backtracking(digits, 0);return result;}
};

3.疑问

字符串类型减个字符型的 '0' 就变成int类型的了??

 int digit = digits[index] - '0';

 C++中用数字表示的字符减去字符 '0'的含义是讲该char类型的字符转换为对应的int类型,

例如;

  1. char S = '5';

  2. int X = S - '0';

  3. cout << X << endl;

X的输出结果是:

x:5

index初始值干嘛要取个0?他是干嘛的??

好像他是层数,用于在终止条件上作比较的,加入数字数量是2,初始是0层,递归一次=1,第二次变成=2,这个时候要进行第三次了。在第三次的递归里碰上终止条件,然后返回,嗯,刚好也可以。

4.记录:

无,待会写下代码,

太晚了,没梳理完,代码也只是过,不过进度要紧。也没有那么多完美的事,尽力完善就好

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_38659.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

[Spring]第二篇:IOC控制反转

简单的说就是,创建对象的权利,或者是控制的位置,由JAVA代码转移到spring容器,由spring的容器控制对象的创建,就是控制反转. spring创建对象时,会读取配置文件,配置文件中主要配置接口和实现类的关系,每个接口对相应一个实现类,使用<bean>标签配置,<bean中的id可以随便…

学生选课系统

项目描述 通过项目背景的分析以及了解到现在学校面临的问题&#xff0c;特别需要一个选课管理系统保证学生信息以及各种课程成绩的准确性和实效性&#xff0c;通过利用计算机的高速计算和快速的统计分析&#xff0c;保证学生信息的最新记录。从教职工的角度老考虑&#xff0c;…

用VS软件开发“中国象棋“游戏<笔记摘录>

整体架构如上 1.很直观地去看这个中国象棋的界面,数一下它有多少行和多少列. 10行,9列:要注意这里数的是安放象棋的位置,有10行9列 这里我们首先想到的必然是二维数组,每一个行列交叉的点都设置成二维数组a[i][j]这样的格式,以此来确定棋盘上面每一个棋子的位置和走向. 我们…

详解 Spring Boot 项目中的配置文件

目录 1. Spring Boot 项目中配日文件的作用是什么 2. Spring Boot 配置文件的两种格式 3. properties 配置文件 3.1 properties 配置文件的基本语法 3.2 properties 配置文件的分类 3.3 如何读取配置文件 3.4 properties 配置文件的优缺点分析 4. yml 配置文件 4.1 yml …

BP神经网络PID从Simulink仿真到PLC控制实现(含博途PLC完整SCL源代码)

单神经元自适应PID控制博途PLC完整源代码,请参看下面的文章链接: 博途PLC单神经元自适应PID控制_RXXW_Dor的博客-CSDN博客_单神经元pid控制1、单神经元作为构成神经网络的基本单位,具有自学习和自适应能力,且结构简单易于计算,传统的PID具有结构简单、调整方便和参数整定…

【软件测试】8年资深测试说出来我们的心声......

目录&#xff1a;导读前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09;前言 执着于手动的功能测…

SSM毕设项目 - 基于SSM的毕业设计管理系统(含源码+论文)

文章目录1 项目简介2 实现效果2.1 界面展示3 设计方案3.1 概述3.2 系统流程3.2.1 系统开发流程3.3.2 教师登录流程3.3.3 系统操作流程3.3 系统结构设计4 项目获取1 项目简介 Hi&#xff0c;各位同学好呀&#xff0c;这里是M学姐&#xff01; 今天向大家分享一个今年(2022)最新…

【Android App】实战项目之仿抖音的短视频分享App(附源码和演示视频 超详细必看)

需要全部代码请点赞关注收藏后评论区留言私信~~~ 与传统的影视行业相比&#xff0c;诞生于移动互联网时代的短视频是个全新行业&#xff0c;它制作方便又容易传播&#xff0c;一出现就成为大街小巷的时髦潮流。 各行各业的人们均可通过短视频展示自己&#xff0c;短小精悍的视频…

社区系统项目复盘-6

文章目录什么是Elasticsearch&#xff1f;Spring是怎么整合Elasticsearch的&#xff1f;开发社区搜索功能Elasticsearch实现全文搜索功能什么是Elasticsearch&#xff1f; Elasticsearch简介 一个分布式的、Restful风格的搜索引擎支持对各种类型的数据的检索搜索速度快&#xf…

基于粒子群算法和遗传算法优化的高速列车横向悬挂

目录 前言 1.高速列车模型 2.优化算法优化模糊PID流程 3.普通PID、优化算法模糊PID仿真对比 3.1 模糊控制器设计 3.2 仿真结果 3.2.1粒子群优化PID 3.2.2粒子群优化模糊PID 3.2.3遗传算法优化模糊PID 4.总结 前言 高速列车&#xff0c;是指最高行驶速度在200km/h 及以…

小知识· Zigbee 简介

1. 介绍 ZigBee是一种近距离、低复杂度、低功耗、低速率、低成本的双向无线通讯技术 ZigBee建立在IEEE 802.15.4标准&#xff08;定义了PHY和MAC层&#xff09;之上&#xff0c;ZigBee联盟对其网络层和应用层进行了标准化 ZigBee协议栈可分为五层 - 物理层&#xff08;PHY&a…

多进程并发服务器

TCP三次握手建立连接错误处理模块&#xff1a;wrap.c,函数声明&#xff1a;wrap.h并发服务器模型&#xff08;多进程&#xff0c;多线程&#xff09; 转换大小写程序 服务端 #include <stdio.h> #include <stdlib.h> #include <sys/types.h> #incl…

Mybatis Plus 多租户id使用

本文就不多逼逼&#xff0c;直接进入正题。 什么是多租户 多租户技术&#xff08;Multi-TenancyTechnology&#xff09;又称多重租赁技术&#xff0c;简称SaaS&#xff0c;是一种软件架构技术&#xff0c;是实现如何在多用户环境下 &#xff08;此处的多用户一般是面向企业用…

Java SPI机制的使用和理解

前言&#xff1a; SPI(Service Provider Interface)&#xff0c;是JDK内置的一种服务提供发现机制&#xff0c;Java中 SPI 机制主要思想是将装配的控制权移到程序之外&#xff0c;在模块化设计中这个机制尤其重要&#xff0c;其核心思想就是解耦 1、大家都知道API&#xff0c;却…

【C++】STL —— map和set的模拟实现

目录 一、基础铺垫 二、基本结构分析 1. 节点结构分析 2. 模板参数中仿函数分析 三、正向迭代器 四、封装完成的红黑树 五、map的模拟实现 六、set的模拟实现 一、基础铺垫 在前面的博客中我们了解了map和set的基本使用&#xff0c;以及对二叉搜索树、AVL树和红黑树的…

IPv6进阶:IPv6 过渡技术之 NAT64(IPv6 节点主动访问 IPv4 节点-地址池方式)

实验拓扑 PC1是IPv4网络的一个节点&#xff0c;处于Trust安全域&#xff1b;PC2是IPv6网络的一个节点&#xff0c;处于Untrust安全域。 实验需求 完成防火墙IPv4、IPv6接口的配置&#xff0c;并将接口添加到相应的安全域&#xff1b;在防火墙上配置NAT64的IPv6前缀3001::/64&…

【毕业设计】30-基于单片机矿井瓦斯_气体浓度_烟雾浓度报警设计(原理图+源代码+仿真+答辩论文+答辩PPT)

【毕业设计】30-基于单片机矿井瓦斯/气体浓度/烟雾浓度报警设计&#xff08;原理图源代码仿真答辩论文答辩PPT&#xff09; 文章目录【毕业设计】30-基于单片机矿井瓦斯/气体浓度/烟雾浓度报警设计&#xff08;原理图源代码仿真答辩论文答辩PPT&#xff09;任务书设计说明书摘要…

网络套接字编程(UDP协议)

文章目录预备知识socket&#xff08;网络套接字&#xff09;编程接口简单的UDP网络程序增加多用户可以互相通信预备知识 网络字节序 大端存储&#xff1a;数据的高字节内容保存在内存的低地址处&#xff0c;数据的低字节内容保存在内存的高地址处 小端存储&#xff1a;数据的高…

global关键字、python实现ATM简单功能

目录 一.局部变量、全局变量 二.global关键字 演示 三.编写ATM程序 要求 详细步骤 存在问题 改进 完整代码 一.局部变量、全局变量 1.什么是局部变量 作用范围在函数内部&#xff0c;在函数外部无法使用 2.什么是全局变量 在函数内部和外部均可使用 3.如何将函数内定…

[附源码]SSM计算机毕业设计校园自行车租售管理系统JAVA

项目运行 环境配置&#xff1a; Jdk1.8 Tomcat7.0 Mysql HBuilderX&#xff08;Webstorm也行&#xff09; Eclispe&#xff08;IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持&#xff09;。 项目技术&#xff1a; SSM mybatis Maven Vue 等等组成&#xff0c;B/S模式 M…