当前位置: 首页 > news >正文

力扣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-电话号码的数字组合 思路代码 题目链接 思路 原题&#xff1a; 给定一个仅包含数字 2-9 的字符串&#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下&#xff08;与电话按键相同&#xff09;。注意 1 不对应任何字母。 输…...

如何处理模型的过拟合和欠拟合问题

好久没有写人工智能这块的东西了&#xff0c;今天正好在家休息&#xff0c;给大家分享一下最近在训练时遇到的过拟合和欠拟合的问题&#xff0c;经过仔细的思考&#xff0c;总结如下&#xff1a; 在处理模型的过拟合和欠拟合问题时&#xff0c;我们需要根据具体情况采取不同的…...

CSRF详解

CSRF&#xff0c;全称是Cross-Site Request Forgery&#xff0c;即跨站请求伪造&#xff0c;也被称为“one click attack”或者session riding&#xff0c;是一种网络攻击方式。它允许攻击者诱导用户在已登录的Web应用程序上执行非预期的操作。 工作原理CSRF攻击通常涉及三个主…...

C# winform 的数据采集,采集周期是间隔10ms、100ms等等,但始终都有1ms的误差,并不是精准的10ms,哪些原因呢

C# winform 的数据采集&#xff0c;采集周期是间隔10ms、100ms等等&#xff0c;但始终都有1ms的误差&#xff0c;并不是精准的10ms&#xff0c;哪些原因呢 在C# WinForms应用程序中进行数据采集时&#xff0c;如果遇到采集周期存在1ms误差的问题&#xff0c;可能的原因包括&am…...

【国内中间件厂商排名及四大中间件对比分析】

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

qt QLocale详解

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

Node.js简介以及安装部署 (基础介绍 一)

Node.js简介 Node.js是运行在服务端的JavaScript。 Node.js是一个基于Chrome JavaScript运行时建立的一个平台。 Node.js是一个事件驱动I/O服务端JavaScript环境&#xff0c;基于Google的V8引擎&#xff0c;V8引擎执行Javascript的速度非常快&#xff0c;性能非常好。 Node.…...

unity实习面

天津小厂 23分钟 下午三点约的面 一直到三点15才面上 估计前边也是在面别人然后面的时间有点长了 唉小厂也是一堆人 上来直接说看项目代码 给看了一下经典tankgame 主要是问了一些其中的代码是什么意思 然后问对象池怎么用 答&#xff1a;光知道不会用 问生命周期函数 得…...

React Native WebView 进阶:实现带回调函数的通讯

实现带回调的通讯 Web 端实现 在网页中&#xff0c;我们使用 window.callbacks 对象来注册回调函数&#xff0c;并将 callbackId 传递给 App&#xff1a; <script>window.callbacks {callbacks: {},register: function(successCallback, errorCallback) {const callb…...

【设计模式】结构型模式(四):组合模式、享元模式

《设计模式之结构型模式》系列&#xff0c;共包含以下文章&#xff1a; 结构型模式&#xff08;一&#xff09;&#xff1a;适配器模式、装饰器模式结构型模式&#xff08;二&#xff09;&#xff1a;代理模式结构型模式&#xff08;三&#xff09;&#xff1a;桥接模式、外观…...

分布式数据库中间件mycat

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

放大电路中的反馈 > 负反馈 > 四种组态 > 虚断和虚短

零、什么是反馈&#xff1f;为什么反馈很重要&#xff1f;而且负反馈最重要&#xff1f; 反馈在所有领域都是很美的东西&#xff1a; 公司出台某项政策&#xff0c;过了一个月让大家谈谈新政策的感受&#xff0c;然后公司对政策进行适当调整。 高三月考可以反应你对各个学课的…...

STM32F405RGT6单片机原理图、PCB免费分享

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

大语言模型鼻祖Transformer的模型架构和底层原理

Transformer 模型的出现标志着自然语言处理&#xff08;NLP&#xff09;技术的一次重大进步。这个概念最初是针对机器翻译等任务而提出的&#xff0c;Transformer 后来被拓展成各种形式——每种形式都针对特定的应用&#xff0c;包括原始的编码器-解码器&#xff08;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&#xff08;Bidirectional Encoder Representations from Transformers&#xff09;&#xff0c;我们将深入探讨它的技术架构、预训练任务、微调方法及其在各种自然语言处理&#xff08;NLP&#xff09;任务中的应用。 一、BERT的技术架构 …...

智能的编织:C++中auto的编织艺术

在C的世界里&#xff0c;auto这个关键字就像是一个聪明的助手&#xff0c;它能够自动帮你识别变量的类型&#xff0c;让你的代码更加简洁和清晰。下面&#xff0c;我们就来聊聊auto这个关键字的前世今生&#xff0c;以及它在C11标准中的新用法。 auto的前世 在C11之前&#x…...

订单分库分表

一、引言 在当今互联网时代&#xff0c;随着电商、金融等行业的快速发展&#xff0c;订单数量呈爆炸式增长。传统的单一数据库存储订单信息的方式面临着巨大的挑战&#xff0c;如数据存储容量有限、查询性能下降、数据备份和恢复困难等。为了解决这些问题&#xff0c;分库分表技…...

【温度表达转化】

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

封装一个web Worker 处理方法实现多线程

背景&#xff1a; 开启多线程处理一段耗时的逻辑 简化Worker使用 直接上代码&#xff1a; 以下是封装的函数直接复制即可 /*** 封装一个worker的启动函数 用于开启一个新的线程 来处理一些耗时的操作* param {object} paremdata 传递给worker的参数* param {function} call…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

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

2021-03-15 iview一些问题

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

ElasticSearch搜索引擎之倒排索引及其底层算法

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

Spring数据访问模块设计

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

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

mac:大模型系列测试

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