力扣17-电话号码的数字组合
力扣17-电话号码的数字组合
- 思路
- 代码
题目链接
思路
原题:
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
输入:digits = “23”
输出:[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”
思路:
电话号码中的一个数字可以对应到多个字母,例如2对应a、b、c。要求23对应的字母组合,就是把2和3对应的字母进行组合。
在每次组合的过程中,一个数字只能取一个字母,不能连续两个字母来自同一个数字;
思考:
问题1:如何收集一个可能的组合?
问题2:在收集到一种组合后,如何继续收集第二种组合?
对于问题1:用暴力法可以解决,每层循环枚举一个数字对应的字母,但是电话号码串很长,循环嵌套深,代码不易好编写
可以采用递归的方式,每层进入递归函数,尝试一个数字对应的点好号码
进入函数,可以想向成进入一棵树的下一层,当递归的深度到达电话号码长度,即到达叶子节点,则返回。
问题3:在递归的每一层做什么?
递归纵向是进入树下一层,即电话号码中的一个数字,在同一层,应该去枚举这个数字对应的字母,这样就可以将当前层的字母,与上一层的字母进行结合,形成答案的一部分,,
问题4:递归什么时候结束?
到达电话号码的长度时,应该往树的上一层返回。
这里的往下递,和往上归,即回溯法,往下遍历是搜索,往上是回溯;回退到上一层,当前数字对应的字母就丢弃了,
比如 2,3; 3是第二层,遍历得到的字母组合是ab, 已经达到电话号码长度,往上一层回溯时b应该就被丢弃。
因此,本题使用回溯法,纵向遍历电话号码中的每个数字,横向遍历每个数字对应的字母,达到电话号码长度时收集一种组合,并往上一层回溯。
代码
class Solution {private List<String> ans;private String[][] dic = {{"2","abc"},{"3","def"},{"4","ghi"},{"5","jkl"},{"6","mno"},{"7","pqrs"},{"8","tuv"},{"9","wxyz"}};public List<String> letterCombinations(String digits) {ans = new ArrayList<>();if (digits.length()==0) {return ans;}Map<String,String> m = new HashMap<>();for (int i=0, n=dic.length; i<n; i++) {m.put(dic[i][0]+"", dic[i][1]+"");}String path = "";dfs(digits, m, 0, path);return ans;}public void dfs(String digits, Map<String, String> mp, int i, String path) {int n = digits.length();if (i>=n) {ans.add(new String(path));return;}String t = mp.get(digits.charAt(i)+"");for (int j=0, m=t.length(); j<m; j++) {dfs(digits, mp, i+1, path+t.charAt(j));}}
}
相关文章:

力扣17-电话号码的数字组合
力扣17-电话号码的数字组合 思路代码 题目链接 思路 原题: 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 输…...

如何处理模型的过拟合和欠拟合问题
好久没有写人工智能这块的东西了,今天正好在家休息,给大家分享一下最近在训练时遇到的过拟合和欠拟合的问题,经过仔细的思考,总结如下: 在处理模型的过拟合和欠拟合问题时,我们需要根据具体情况采取不同的…...
CSRF详解
CSRF,全称是Cross-Site Request Forgery,即跨站请求伪造,也被称为“one click attack”或者session riding,是一种网络攻击方式。它允许攻击者诱导用户在已登录的Web应用程序上执行非预期的操作。 工作原理CSRF攻击通常涉及三个主…...
C# winform 的数据采集,采集周期是间隔10ms、100ms等等,但始终都有1ms的误差,并不是精准的10ms,哪些原因呢
C# winform 的数据采集,采集周期是间隔10ms、100ms等等,但始终都有1ms的误差,并不是精准的10ms,哪些原因呢 在C# WinForms应用程序中进行数据采集时,如果遇到采集周期存在1ms误差的问题,可能的原因包括&am…...

【国内中间件厂商排名及四大中间件对比分析】
国内中间件厂商排名 随着新兴技术的涌入,一批国产中间件厂商破土而出,并在短时间内迅速发展,我国中间件市场迎来洗牌,根据市占率,当前我国中间件厂商排名依次为:东方通、宝兰德、中创股份、金蝶天燕、普元…...

qt QLocale详解
1、概述 QLocale是Qt框架中的一个类,用于处理与本地化相关的操作。它能够方便地实现日期、时间、数字和货币的格式化和解析,支持不同的语言、区域设置和字符集。QLocale提供了一种跨平台的方式来获取当前系统的语言设置,并返回该语言的本地化…...

Node.js简介以及安装部署 (基础介绍 一)
Node.js简介 Node.js是运行在服务端的JavaScript。 Node.js是一个基于Chrome JavaScript运行时建立的一个平台。 Node.js是一个事件驱动I/O服务端JavaScript环境,基于Google的V8引擎,V8引擎执行Javascript的速度非常快,性能非常好。 Node.…...
unity实习面
天津小厂 23分钟 下午三点约的面 一直到三点15才面上 估计前边也是在面别人然后面的时间有点长了 唉小厂也是一堆人 上来直接说看项目代码 给看了一下经典tankgame 主要是问了一些其中的代码是什么意思 然后问对象池怎么用 答:光知道不会用 问生命周期函数 得…...
React Native WebView 进阶:实现带回调函数的通讯
实现带回调的通讯 Web 端实现 在网页中,我们使用 window.callbacks 对象来注册回调函数,并将 callbackId 传递给 App: <script>window.callbacks {callbacks: {},register: function(successCallback, errorCallback) {const callb…...

【设计模式】结构型模式(四):组合模式、享元模式
《设计模式之结构型模式》系列,共包含以下文章: 结构型模式(一):适配器模式、装饰器模式结构型模式(二):代理模式结构型模式(三):桥接模式、外观…...

分布式数据库中间件mycat
MyCat MyCat是一个开源的分布式数据库系统,它实现了MySQL协议,可以作为数据库代理使用。 MyCat(中间件)的核心功能是分库分表,即将一个大表水平分割为多个小表,存储在后端的MySQL服务器或其他数据库中。 它不仅支持MySQLÿ…...

放大电路中的反馈 > 负反馈 > 四种组态 > 虚断和虚短
零、什么是反馈?为什么反馈很重要?而且负反馈最重要? 反馈在所有领域都是很美的东西: 公司出台某项政策,过了一个月让大家谈谈新政策的感受,然后公司对政策进行适当调整。 高三月考可以反应你对各个学课的…...

STM32F405RGT6单片机原理图、PCB免费分享
大学时机创比赛时画的板子,比到一半因为疫情回家,无后续,,,已打板验证过,使用stm32f405rgt6做主控 下载文件资源如下 原理图文件 pcb文件 外壳模型文件 stm32f405例程 功能 以下功能全部验证通过 4路…...

大语言模型鼻祖Transformer的模型架构和底层原理
Transformer 模型的出现标志着自然语言处理(NLP)技术的一次重大进步。这个概念最初是针对机器翻译等任务而提出的,Transformer 后来被拓展成各种形式——每种形式都针对特定的应用,包括原始的编码器-解码器(encoder-de…...

GB/T 43206—2023信息安全技术信息系统密码应用测评要求(五)
文章目录 附录AA.1 概述A.2 密钥产生A.3 密钥分发A.4 密钥存储A.5 密钥使用A.6 密钥更新A.7 密钥归档A. 8 密钥撤销A.9 密钥备份A.10 密钥恢复A.11 密钥销毁 附录B附录C 附录A A.1 概述 密钥管理对于保证密钥全生存周期的安全性至关重要 ,可以保证密钥(除公开密钥外) 不被非授…...
深度学习:BERT 详解
BERT 详解 为了全面详细地解析BERT(Bidirectional Encoder Representations from Transformers),我们将深入探讨它的技术架构、预训练任务、微调方法及其在各种自然语言处理(NLP)任务中的应用。 一、BERT的技术架构 …...

智能的编织:C++中auto的编织艺术
在C的世界里,auto这个关键字就像是一个聪明的助手,它能够自动帮你识别变量的类型,让你的代码更加简洁和清晰。下面,我们就来聊聊auto这个关键字的前世今生,以及它在C11标准中的新用法。 auto的前世 在C11之前&#x…...
订单分库分表
一、引言 在当今互联网时代,随着电商、金融等行业的快速发展,订单数量呈爆炸式增长。传统的单一数据库存储订单信息的方式面临着巨大的挑战,如数据存储容量有限、查询性能下降、数据备份和恢复困难等。为了解决这些问题,分库分表技…...

【温度表达转化】
【温度表达转化】 C语言代码C代码Java代码Python代码 💐The Begin💐点点关注,收藏不迷路💐 利用公式 C5∗(F−32)/9 (其中C表示摄氏温度,F表示华氏温度) 进行计算转化。 输出 输出一行&#x…...

封装一个web Worker 处理方法实现多线程
背景: 开启多线程处理一段耗时的逻辑 简化Worker使用 直接上代码: 以下是封装的函数直接复制即可 /*** 封装一个worker的启动函数 用于开启一个新的线程 来处理一些耗时的操作* param {object} paremdata 传递给worker的参数* param {function} call…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...

Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...

2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...

ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...
嵌入式常见 CPU 架构
架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集,单周期执行;低功耗、CIP 独立外设;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel(原始…...

mac:大模型系列测试
0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何,是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试,是可以跑通文章里面的代码。训练速度也是很快的。 注意…...