当前位置: 首页 > 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…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

Axure 下拉框联动

实现选省、选完省之后选对应省份下的市区...

鸿蒙HarmonyOS 5军旗小游戏实现指南

1. 项目概述 本军旗小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;采用DevEco Studio实现&#xff0c;包含完整的游戏逻辑和UI界面。 2. 项目结构 /src/main/java/com/example/militarychess/├── MainAbilitySlice.java // 主界面├── GameView.java // 游戏核…...