算法第十三天-解码方法

2024-01-08 07:12

本文主要是介绍算法第十三天-解码方法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

解码方法

题目要求


解题思路

来自【宫水三叶】

基本分析

我们称一个解码内容为一个item
根据题意,每个item可以由一个数字组成,也可以由两个数字组成。
数据范围为100,很具有迷惑性,可能会有不少同学会想使用DFS进行暴力搜索。
我们可以大致分析一下这样子的做法是否可行:不失为一般性的考虑字符串s中的任意位置i,位置i既可以作为一个独立item,也可以与上一位置组成新item,那么相当于每个位置都有两种分割选择(先不考虑分割结果的合法性问题),这样子做法的复杂度是 O ( 2 n ) O(2^n) O(2n)的,当n范围是100时,远超我们计算机单秒运算量 ( 1 0 7 ) (10^7) (107)。及时我们将[判断分割结果是否合法]的操作放到暴力搜索过程中做剪枝,也与我们的单秒运算量相差很远。
递归的方法不可行,我们需要考虑递推的解法。

动态规划

这其实时一道字符串类的动态规划题,不难发现对于字符串s的某个位置i而言,我们只关心[位置i自己能否形成独立item]和[位置i能够与上一位置(i-1)能否形成item],而不关心i-1之前的位置。

有了以上分析,我们可以从前往后处理字符串s,使用一个数组记录以字符串s的每一位作为结果的解码方案数。即定义 f [ i ] f[i] f[i]为考虑前i个字符的解码方案数。
对于字符串s的任意位置i而言,其存在三种情况:

  • 只能由位置i的单独作为一个item,设为a,转移的前提是a的数值范围为[1,9],转移逻辑为f[i] = f[i-1].
  • 只能由位置i的与前一位置(i-1)共同作为一个item,设为b,转移的前提时b的数值范围为[10,26],转移逻辑为f[i] = f[i-2]
  • 位置i既能作为独立item也能与上一位置形成item,转移逻辑为f[i] = f[i-1] +f[i-2]
    因此,我们有如下转移方程:
    { f [ i ] = f [ i − 1 ] , 1 ≤ a ≤ 9 f [ i ] = f [ i − 2 ] , 10 ≤ b ≤ 26 f [ i ] = f [ i − 1 ] + f [ i − 2 ] , 1 ≤ a ≤ 9 , 10 ≤ b ≤ 26 \left\{\begin{aligned} f[i] = f[i-1],1\le a \le 9\\ f[i] = f[i-2],10\le b \le 26\\ f[i] = f[i-1]+f[i-2],1\le a \le 9,10\le b \le 26\\ \end{aligned} \right. f[i]=f[i1],1a9f[i]=f[i2],10b26f[i]=f[i1]+f[i2],1a9,10b26
    其他细节:由于本题存在前导零,而前导零属于无效item。可以进行特判,但个人习惯往字符串头部追加空格作为哨兵,追加空格既可以避免讨论前导零,也能使下标从1开始,简化f[i-1]等负数下标的判断。

代码

class Solution:def numDecodings(self, s: str) -> int:n = len(s)s = ' ' + sf =[0] *(n+1)f[0]=1for i in range(1,n+1):a = ord(s[i])-ord('0')b = (ord(s[i-1]) -ord('0')) * 10 + ord(s[i])-ord('0')if 0<a<=9:f[i] =f[i-1]if 10<=b<=26:f[i] +=f[i-2]return f[n]

复杂度分析

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( n ) O(n) O(n)

空间优化

不难发现,我们转移f[i]时只依赖f[i-1] 和 f[i-2]两个状态。因此我们可以采用与[滚动数组]类似的思路,只创建长度为3的数组,通过取余的方式来复用不再需要的下标。

代码

class Solution:def numDecodings(self, s: str) -> int:n = len(s)s = ' ' + sf = [0] * 3f[0] = 1for i in range(1,n + 1):f[i % 3] = 0a = ord(s[i]) - ord('0')b = ( ord(s[i - 1]) - ord('0') ) * 10 + ord(s[i]) - ord('0')if 1 <= a <= 9:f[i % 3] = f[(i - 1) % 3]if 10 <= b <= 26:f[i % 3] += f[(i - 2) % 3]return f[n % 3]

复杂度分析

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)

这篇关于算法第十三天-解码方法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/582668

相关文章

Maven 配置中的 <mirror>绕过 HTTP 阻断机制的方法

《Maven配置中的<mirror>绕过HTTP阻断机制的方法》:本文主要介绍Maven配置中的<mirror>绕过HTTP阻断机制的方法,本文给大家分享问题原因及解决方案,感兴趣的朋友一... 目录一、问题场景:升级 Maven 后构建失败二、解决方案:通过 <mirror> 配置覆盖默认行为1. 配置示

SpringBoot排查和解决JSON解析错误(400 Bad Request)的方法

《SpringBoot排查和解决JSON解析错误(400BadRequest)的方法》在开发SpringBootRESTfulAPI时,客户端与服务端的数据交互通常使用JSON格式,然而,JSON... 目录问题背景1. 问题描述2. 错误分析解决方案1. 手动重新输入jsON2. 使用工具清理JSON3.

使用jenv工具管理多个JDK版本的方法步骤

《使用jenv工具管理多个JDK版本的方法步骤》jenv是一个开源的Java环境管理工具,旨在帮助开发者在同一台机器上轻松管理和切换多个Java版本,:本文主要介绍使用jenv工具管理多个JD... 目录一、jenv到底是干啥的?二、jenv的核心功能(一)管理多个Java版本(二)支持插件扩展(三)环境隔

Java中Map.Entry()含义及方法使用代码

《Java中Map.Entry()含义及方法使用代码》:本文主要介绍Java中Map.Entry()含义及方法使用的相关资料,Map.Entry是Java中Map的静态内部接口,用于表示键值对,其... 目录前言 Map.Entry作用核心方法常见使用场景1. 遍历 Map 的所有键值对2. 直接修改 Ma

Mybatis Plus Join使用方法示例详解

《MybatisPlusJoin使用方法示例详解》:本文主要介绍MybatisPlusJoin使用方法示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,... 目录1、pom文件2、yaml配置文件3、分页插件4、示例代码:5、测试代码6、和PageHelper结合6

Java中实现线程的创建和启动的方法

《Java中实现线程的创建和启动的方法》在Java中,实现线程的创建和启动是两个不同但紧密相关的概念,理解为什么要启动线程(调用start()方法)而非直接调用run()方法,是掌握多线程编程的关键,... 目录1. 线程的生命周期2. start() vs run() 的本质区别3. 为什么必须通过 st

C#之List集合去重复对象的实现方法

《C#之List集合去重复对象的实现方法》:本文主要介绍C#之List集合去重复对象的实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C# List集合去重复对象方法1、测试数据2、测试数据3、知识点补充总结C# List集合去重复对象方法1、测试数据

SpringBoot读取ZooKeeper(ZK)属性的方法实现

《SpringBoot读取ZooKeeper(ZK)属性的方法实现》本文主要介绍了SpringBoot读取ZooKeeper(ZK)属性的方法实现,强调使用@ConfigurationProperti... 目录1. 在配置文件中定义 ZK 属性application.propertiesapplicati

MyBatis设计SQL返回布尔值(Boolean)的常见方法

《MyBatis设计SQL返回布尔值(Boolean)的常见方法》这篇文章主要为大家详细介绍了MyBatis设计SQL返回布尔值(Boolean)的几种常见方法,文中的示例代码讲解详细,感兴趣的小伙伴... 目录方案一:使用COUNT查询存在性(推荐)方案二:条件表达式直接返回布尔方案三:存在性检查(EXI

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢?今天,我们... 目录方法1:C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1:创建C#类库(.NET