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

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Python常用模块:time、os、shutil与flask初探

一、Flask初探 & PyCharm终端配置 目的: 快速搭建小型Web服务器以提供数据。 工具: 第三方Web框架 Flask (需 pip install flask 安装)。 安装 Flask: 建议: 使用 PyCharm 内置的 Terminal (模拟命令行) 进行安装,避免频繁切换。 PyCharm Terminal 配置建议: 打开 Py…...

基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究

摘要&#xff1a;在消费市场竞争日益激烈的当下&#xff0c;传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序&#xff0c;探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式&#xff0c;分析沉浸式体验的优势与价值…...

VSCode 使用CMake 构建 Qt 5 窗口程序

首先,目录结构如下图: 运行效果: cmake -B build cmake --build build 运行: windeployqt.exe F:\testQt5\build\Debug\app.exe main.cpp #include "mainwindow.h"#include <QAppli...

性能优化中,多面体模型基本原理

1&#xff09;多面体编译技术是一种基于多面体模型的程序分析和优化技术&#xff0c;它将程序 中的语句实例、访问关系、依赖关系和调度等信息映射到多维空间中的几何对 象&#xff0c;通过对这些几何对象进行几何操作和线性代数计算来进行程序的分析和优 化。 其中&#xff0…...

IP选择注意事项

IP选择注意事项 MTP、FTP、EFUSE、EMEMORY选择时&#xff0c;需要考虑以下参数&#xff0c;然后确定后选择IP。 容量工作电压范围温度范围擦除、烧写速度/耗时读取所有bit的时间待机功耗擦写、烧写功耗面积所需要的mask layer...