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

91. 解码方法 ——【Leetcode每日刷题】

91. 解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 :

‘A’ -> “1”
‘B’ -> “2”

‘Z’ -> “26”

解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,“11106” 可以映射为:

“AAJF” ,将消息分组为 (1 1 10 6)
“KJF” ,将消息分组为 (11 10 6)
注意,消息不能分组为 (1 11 06) ,因为 “06” 不能映射为 “F” ,这是由于 “6” 和 “06” 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1:

输入:s = “12”
输出:2
解释:它可以解码为 “AB”(1 2)或者 “L”(12)。

示例 2:

输入:s = “226”
输出:3
解释:它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

示例 3:

输入:s = “06”
输出:0
解释:“06” 无法映射到 “F” ,因为存在前导零(“6” 和 “06” 并不等价)。

提示:

  • 1 <= s.length <= 100
  • s 只包含数字,并且可能包含前导零。

思路:(动态规划)

这道题不要往复杂了想,其实一共就是两种情况,一次解码一个字符和一次解码两个字符,dp[i] 就等于这两种情况之和。

dp数组的含义,dp[i] 为前 i 个子字符串 (即从 0 ~ i-1) 一共有多少种编码方式。

递推公式为:
dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i - 1] + dp[i - 2]dp[i]=dp[i1]+dp[i2]

特别需要注意的是:

  1. 如果 s[i] = 0 ,不能单独解码,只能和前一个组合解码,前一个 s[i-1] 必须是 1 或者 2,否则超出范围无法解码。
    • 如果可以前一个字符s[i-1]组合解码,则s[i-1]就不能和s[i-2]在组合了,此时:dp[i] = dp[i -2];
    • 如果不能组合解码,则该字符串无法解码。
  2. 如果 s[i] 不为0,则肯定可以单独解码,能否组合解码,还要判断组合码是否超出边界,或者无法映射。
    • 如果 s[i] 可以组合解码则: dp[i] = dp[i - 1] + dp[i - 2] ;
    • 不能组合解码则: dp[i] = dp[i - 1] 。

代码:(Java)

public class DecodingWays {public static void main(String[] args) {// TODO Auto-generated method stubString s = "226";System.out.println(numDecodings(s));}public static int numDecodings(String s) {int n = s.length();if(s.charAt(0) == '0')return 0;int []dp = new int[n + 1];dp[0] = dp[1] = 1;for(int i = 1; i < n; i++) {if(s.charAt(i) == '0' && (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2')) {dp[i + 1] = dp[i - 1];}else if(s.charAt(i) == '0') {return 0;}else if(Integer.valueOf(s.substring(i - 1,i + 1)) < 27 && Integer.valueOf(s.substring(i - 1,i + 1)) > 10) {dp[i + 1] = dp[i] + dp[i - 1];}else {dp[i + 1] = dp[i];}}return dp[n];}
}

运行结果:

在这里插入图片描述

复杂度分析

  • 时间复杂度:O(n),其中 n 是字符串 s 的长度。

  • 空间复杂度:O(n)。使用数组进行状态转移,其中 n 是字符串 s 的长度;

注:仅供学习参考!

题目来源:力扣。

相关文章:

91. 解码方法 ——【Leetcode每日刷题】

91. 解码方法 一条包含字母 A-Z 的消息通过以下映射进行了 编码 &#xff1a; ‘A’ -> “1” ‘B’ -> “2” … ‘Z’ -> “26” 要 解码 已编码的消息&#xff0c;所有数字必须基于上述映射的方法&#xff0c;反向映射回字母&#xff08;可能有多种方法&#xff0…...

人体存在传感器成品方案,精准感知静止存在,实时智能化感控技术

随着现今智能时代的发展&#xff0c;酒店也越来越趋于智能化&#xff0c;也在不断地推行智慧酒店&#xff0c;这也给人们入住酒店提供了良好的体验。 人体存在感知是智能酒店中极其重要的一项应用技术&#xff0c;只有智能设备通过精准地感知人体存在&#xff0c;才能更好地做…...

mysql连接池的实现

目录 1 池化技术 2 什么是数据库连接池 3 为什么使用数据库连接池 3.1 不使用连接池 3.2 使用连接池 3.3 长连接和连接池的区别 4 数据库连接池运行机制 5 连接池和线程池的关系 6 线程池设计要点 6.1 连接池设计逻辑 构造函数 初始化 请求获取连接 归还连接 析…...

哪种类型蓝牙耳机佩戴最舒服?舒适度最好的蓝牙耳机推荐

如果您想在外出时听自己喜欢的音乐&#xff0c;您需要佩戴耳机&#xff0c;当前的耳机都足够小&#xff0c;可以将它们放在口袋里&#xff0c;即使它们在充电盒中也是如此&#xff0c;舒适度一直都是人们所追求的&#xff0c;舒适之余&#xff0c;佩戴同样稳固更加令人安心&…...

2020蓝桥杯真题洁净数 C语言/C++

题目描述 小明非常不喜欢数字 2&#xff0c;包括那些数位上包含数字 2 的数。如果一个数的数位不包含数字 2&#xff0c;小明将它称为洁净数。 请问在整数 1 至 n 中&#xff0c;洁净数有多少个&#xff1f; 输入描述 输入的第一行包含一个整数 n(1≤n≤10^6)。 输出描述 输…...

【随笔二】useReducer详解及其应用场景

前言 useReducer 实际上是 useState 的升级版&#xff0c;都是用来存储和更新 state&#xff0c;只是应用的场景不一样。 一般情况下&#xff0c;我们使用 useState 就足够项目需要了&#xff0c;不多当遇到以下场景时&#xff0c;使用useReducer 会更好些 。 状态逻辑复杂&…...

打怪升级之istringstream介绍

istringstream类 istringstream本质不是类&#xff0c;是一个宏&#xff0c;或者说是一个流&#xff1a; typedef basic_istringstream<char> istringstream;istringstream从basic_istringstream的char专用项而来。这一部分让人看得摸不着头脑的原因是因为大量使用了st…...

系统重装漏洞

zzcms系统重装漏洞 一、配置zzcms环境 1. 使用小皮搭建zzcms框架 2. 安装zzcms 按照下面的操作进行,傻瓜式操作即可 3. 打开网站 二、漏洞利用 在访问install目录的默认文件后,会出现zzcms安装向导 http://www.zzcms.com/install/index.php 但是会显示 “安装向导…...

C++面向对象编程之五:友元(friend)

C中&#xff0c;允许一个类的非共有成员被这个类授予友元&#xff08;friend&#xff09;关系的全局函数&#xff0c;另一个类&#xff0c;或另一个类中的成员函数访问。友元不是一个类中的成员&#xff0c;所以它们不受声明出现部分的访问权限&#xff08;public&#xff0c;p…...

[手写OS]动手实现一个OS 之X86实模式下的汇编开发

[手写OS]动手实现一个OS 之X86实模式下的汇编开发 x86实模式下 汇编开发是一个 intel x86实模式中的汇编程序开发类型。它涉及操纵几个16位处理器寄存器&#xff0c;并仅处理内存中的物理地址&#xff08;与受保护模式相对&#xff09;。 这种类型的编程中最广为人知的应用就…...

【Linux内核二】常用的网络丢包错包debug工具介绍

目录 ifconfig Ifconfig输出各字段简述 txqueuelen RX和TX的errors指哪些错误 dropped与overruns的区别 常用ifconfig配置命令 显示网卡信息 启动关闭指定网卡 配置和删除ip地址 修改MAC地址 启用和关闭ARP协议 设置最大传输单元 设置网卡的promiscuous模式 设置…...

qt控件增加渐变色效果

ui->returnBtn->setStyleSheet("color: rgb(0, 0, 0);""background:qlineargradient(spread:pad, x1:0, y1:1, x2:0, y2:0, ""stop:0 #5f5f5f, stop:0.5 #ffffff, stop:0.98 #5f5f5f);""border:none;");效果如下图&#xff1a; …...

【node : 无法将“node”项识别为 cmdlet、函数、脚本文件或可运行程序的名称。 最全面有效的解决方案】

执行nodejs文件错误&#xff1a; 这个错误提示通常是由于你的系统无法识别 "node" 命令&#xff0c;可能是由于你没有正确地安装或配置 Node.js 环境变量。 问题描述 ​​​​​​​​​​​​​​ 原因分析&#xff1a; 可能原因包括&#xff1a; 1.Node.js未正确安…...

打怪升级之字符串的分界符与字符串替换

流的字符串分界符 在C的iostream中&#xff0c;有流的字符串分界符&#xff1a; " “和”"都代表简单的分隔。 因此&#xff0c;使用流来做字符串分隔的话&#xff0c;有一个比较简单的方案就是将原定义的分隔符通过替换的方式变成流的分隔符。然后再录入流中就能…...

载荷台子使用方式

载荷自动测量台子使用方法 电源开关旋转到1&#xff0c;开启电源开启台子微机开关&#xff0c;开启电脑&#xff08;winxp&#xff09;开启台子载荷开关&#xff0c;启动载荷台子点击电脑动标图标&#xff0c;开启软件放入载荷&#xff0c;弹性体向上&#xff0c;载荷台子压头压…...

1005 继续(3n + 1)猜想

卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里&#xff0c;情况稍微有些复杂。 当我们验证卡拉兹猜想的时候&#xff0c;为了避免重复计算&#xff0c;可以记录下递推过程中遇到的每一个数。例如对 n3 进行验证的时候&#xff0c;我们需要计算 3、5、8、4、2、1&a…...

VMware15配置NAT模式联通网络

最近为了测试C# 开发的桌面应用程序悬浮球的兼容性&#xff0c;在虚拟机上安装了win7系统和xp系统&#xff0c;之前也安装过黑苹果系统&#xff0c;但是win系统倒是第一次安装&#xff0c;在win7系统联网的时候&#xff0c;踩了一些坑&#xff0c;整理纪录一下。 设置主物理机配…...

doPost的实际使用

目录 前言 一、doPost是什么&#xff1f; 二、使用步骤 1.doPost的请求方法 2.需要引入依赖 总结 前言 本章主要记录一下doPost的请求公用方法的使用。 一、doPost是什么&#xff1f; 它其实就是一个http的post请求方式。 二、使用步骤 1.doPost的请求方法 当我们系…...

2017年MathorCup数学建模A题流程工业的智能制造解题全过程文档及程序

2017年第七届MathorCup高校数学建模挑战赛 A题 流程工业的智能制造 原题再现&#xff1a; “中国制造 2025”是我国制造业升级的国家大战略。其技术核心是智能制造&#xff0c;智能化程度相当于“德国工业 4.0”水平。“中国制造 2025”的重点领域既包含重大装备的制造业&…...

HNU-电子测试平台与工具2-数模转换

数模转换实验 计科XXXX wolf 工程文件我也一并上传了 D级任务 一.实验任务 对74194进行仿真验证&#xff0c;掌握Quartus仿真的基本原则和常规步骤&#xff0c;记录移位寄存器的数据读写&#xff0c;并描述仿真波形&#xff0c;分析结果。 二.实验过程 1.电路连接 2.功能…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...