动态规划算法题目练习——91.解码方法
1.题目解析
题目来源:91.解码方法——力扣

测试用例

2.算法原理
基础版本
1.状态表示
由于题目只要求返回第i个位置的可能情况,则只需要开辟n(n=s.size())个大小的dp表即可
2.状态转移方程
题目可知第i个位置可以单独解码也可以与前一个位置组合解码,所以两种情况都需要讨论,当满足单独解码就加上前i-1个位置所有的可能性即可,当也满足与前一个位置组合解码就再加上前i-2个位置的所有可能性即可
3.初始化
需要初始化开始两个位置的值,其中dp[0]只需要判断第一个字符s[0]是否为'0'即可,为0则不能解码,dp[0]=0,反之可以解码则dp[0]=1
但是需要注意dp[1]需要判断的它本身是否可以单独解码还要判断是否可以和前一个位置组合解码
4.细节处理
需要注意这种解法不能处理n为1时的情况,需要单独处理n=1时返回dp[0]的值
5.返回值
由于只用返回第i个位置的可能性,所以映射的下标就是n-1,最后返回dp[n-1]即可

优化版本
1.状态表示
前面的基础版本中对于第二个位置的初始化有些多余,不如只用初始化第一个dp表的位置即可,所以这里使用虚拟位置来优化
由于多了一个虚拟位置,就需要创建dp(n+1)的dp表,第一个位置用作虚拟位置,此时对应的第i个位置映射的下标也为i,更加清晰
2.状态转移方程
这里主要讲解的是对于虚拟位置的值如何确定,首先dp[1]也就是原来的dp[0],直接初始化即可,但是如果要借助状态转移方程初始化dp[2]的时候,需要用到虚拟位置的情况就是在组合解码时,,也就是dp[2] += dp[2-2]时,此时因为已经确定了dp[2-1]可以与dp[2]组合解码也就是说dp[2-1]!='0',这时将dp[0]虚拟位置置为1即可
3.初始化
简化了之后只用初始化除虚拟位置的第一个位置即可
4.细节处理
dp表多了一个虚拟位置但是s字符串没有,所以需要在基础版本的情况下将s的映射-1
5.返回值
dp表多开了一个位置,直接返回dp[n]即可
3.实战代码
初始版本
class Solution {
public:int numDecodings(string s) {int n = s.size();//dp表默认初始化为0 vector<int> dp(n);dp[0] = (s[0] != '0');//特殊处理边界情况if(n == 1){return dp[0];}//当前两个数字都可以单独编码则加一种情况if(s[0] != '0' && s[1] != '0'){dp[1] += 1;}//当前两位可以组合编码则多一种情况int t = (s[0] - '0') * 10 + s[1] - '0';if(t >= 10 && t <= 26){dp[1] += 1;}for(int i = 2;i < n;i++){//当前位置可以单独编码if(s[i] != '0'){dp[i] += dp[i-1];}//当前位置可以和前一个位置组合编码int t = (s[i - 1] - '0') * 10 + s[i] - '0';if(t >= 10 && t <= 26){dp[i] += dp[i-2];}}//返回第n个位置,映射下标为n-1return dp[n-1];}
};
优化版本
class Solution {
public:int numDecodings(string s) {int n = s.size();vector<int> dp(n+1);//将新加入的位置置为1dp[0] = 1;//将原来的第一个位置的初始值右移dp[1] = (s[1-1] != '0');for(int i = 2;i <= n;i++){//当第i个位置可以单独解码则加上前i-1个位置的可能性//第i个位置的映射下标为i-1if(s[i-1] != '0'){dp[i] += dp[i - 1];}//当第i个位置可以与前一个位置组合解码则加上前i-2个位置的可能性//注意不能有前导0,所以t从10开始限制范围int t = (s[i-2] - '0')*10 + s[i-1] - '0';if(t >= 10 && t <= 26){dp[i] += dp[i-2];}}return dp[n];}
};
相关文章:
动态规划算法题目练习——91.解码方法
1.题目解析 题目来源:91.解码方法——力扣 测试用例 2.算法原理 基础版本 1.状态表示 由于题目只要求返回第i个位置的可能情况,则只需要开辟n(ns.size())个大小的dp表即可 2.状态转移方程 题目可知第i个位置可以单独解码也可以与前一个位置组合解码&am…...
每天一个数据分析题(四百九十二)- 主成分分析与因子分析
在因子分析中,因子载荷矩阵是用来表示( )。 A. 变量和因子之间的关系 B. 样本和因子之间的关系 C. 变量和样本之间的关系 D. 因子和因子之间的关系 数据分析认证考试介绍:点击进入 题目来源于CDA模拟题库 点击此处获取答案…...
Linux shell编程学习笔记86:sensors命令——硬件体温计
0 引言 同事们使用的Windows系统电脑,经常莫名其妙地装上了鲁大师,鲁大师的一项功能是显示系统cpu等硬件的温度。 在Linux系统中,sensors命令可以提供类似的功能。 1 sensors命令 的安装和配置 1.1 sensors命令 的安装 要使用sensors命…...
基于SSM车位租赁系统【附源码】
基于SSM车位租赁系统 效果如下: 注册页面 首页展示 车位租赁订单展示 车位列表页面 公告信息管理页面 公告类型管理界面 研究背景 随着经济的持续增长和城市化进程的加速,土地资源变得日益紧缺,停车难问题已成为许多城市面临的共同挑战。随…...
JAVA开源项目 新生报到网站 计算机毕业设计
本文项目编号 T 002 ,文末自助获取源码 \color{red}{T002,文末自助获取源码} T002,文末自助获取源码 目录 一、系统介绍二、演示录屏三、启动教程四、功能截图五、文案资料5.1 选题背景5.2 国内外研究现状5.3 可行性分析 六、核心代码6.1 提…...
QT将QBytearray的data()指针赋值给结构体指针变量后数据不正确的问题
1、问题代码 #include <QCoreApplication>#pragma pack(push, 1) typedef struct {int a; // 4字节float b; // 4字节char c; // 1字节int *d; // 8字节 }testStruct; #pragma pack(pop)#include <QByteArray> #include <QDebug>int main() {testStruct …...
修改银河麒麟操作系统V10(SP1)网卡名称为ethx
修改银河麒麟桌面操作系统V10(SP1)网卡名称为ethx 步骤一:查看当前网卡信息步骤二:修改GRUB配置文件步骤三:更新GRUB配置步骤四:编辑网络接口文件步骤五:重启机器 💖The Begin&#…...
MySQL多表查询:标量子查询
先看我的emp表结构 emp表 子查询基本语法 select * from t1 where column1 (select column1 from t2);例子1:查询"销售部" 的所有员工信息 这个可以先拆解为两个 a.查询"销售部"的部门ID select id from dept where name 销售部; b. 根…...
C++学习笔记----8、掌握类与对象(六)---- 操作符重载(1)
经常在对象上执行如相加,比较,文件传输等操作。例如,spreadsheet只有在可以在上面执行自述运算才有用,比如对整行的单元格求和。所有这些都可以通过重载操作符来完成。 许多人发现操作符重载的语法复杂而令人迷惑。至少一开始是这…...
Ascend C 自定义算子开发:高效的算子实现
Ascend C 自定义算子开发:高效的算子实现 在 Ascend C 平台上,开发自定义算子能够充分发挥硬件的性能优势,帮助开发者针对不同的应用场景进行优化。本文将以 AddCustom 算子为例,介绍 Ascend C 中自定义算子的开发流程及关键技术…...
面向对象技术——设计模式
目录 层次结构 具体设计模式分类 创建型模式(处理创建对象) 结构型模式(处理类和对象的组合) 行为型模式(描述类或者对象的交互行为) 创建型设计模式 编辑 结构型设计模式 行为型设计模式编辑 …...
2024 Mysql基础与进阶操作系列之MySQL触发器详解(20)作者——LJS[你个小黑子这都还学不会嘛?你是真爱粉嘛?真是的 ~;以后请别侮辱我家鸽鸽]
欢迎各位彦祖与热巴畅游本人专栏与博客 你的三连是我最大的动力 以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现] 专栏跑道一 ➡️ MYSQL REDIS Advance operation 专栏跑道二➡️ 24 Network Security -LJS 专栏跑道三 ➡️HCIP;H3C-SE;CCIP——…...
找不到concrt140.dll如何修复,快来试试这6种解决方法
concrt140.dll是微软Visual C 2015 Redistributable Package中的一个重要动态链接库文件,它在许多Windows应用程序中扮演着关键角色。本文将详细探讨concrt140.dll丢失的原因、影响、解决方法以及预防措施,帮助用户更好地理解和应对这一问题。 一、什么是…...
年会工作会议会务报名签到小程序开源版开发
年会工作会议会务报名签到小程序开源版开发 会议管理微信小程序,对会议流程、开支、数量、标准、供应商提供一种标准化的管理方法。以达到量化成本节约,风险缓解和服务质量提升的目的。适用于大型论坛、峰会、学术会议、政府大会、合作伙伴大会、经销商…...
UE C++ 实时加载模型的总结
一.总体思路: 如果实时加载UE模型,需要先将之前的模型删除。再生成出来,放在根节点,保持相对位置,相对的俯仰角。 void AAirForce::LoadWeapon(int ID, int Type, double X, double Y, double Z) {//m_weaponMap.Emp…...
实施威胁暴露管理、降低网络风险暴露的最佳实践
随着传统漏洞管理的发展,TEM 解决了因攻击面扩大和安全工具分散而产生的巨大风险。 主动式 TEM 方法优先考虑风险并与现有安全工具无缝集成,使组织能够在威胁被有效利用之前缓解威胁。 为什么威胁暴露管理 (TEM) 在现代网络安全策略中变得至关重要&…...
51.哀家要长脑子了!
1.P1003 [NOIP2011 提高组] 铺地毯 重复 模拟 要求覆盖在最上面的地毯编号,用四个数组abgk分别记录地毯起点的左下角横纵坐标,地毯的长度宽度,输入的坐标x y 当它满足大于等于左下角坐标 并且 小于等于 地毯左下角横纵坐标的时候…...
Overleaf 无法显示图片
问题描述 在Overleaf中的代码为: \begin{figure}\centering\includegraphics[width0.98\linewidth]{figures/test.png}\caption{This is a test.}\label{fig:test} \end{figure}但无法正常显示图片: 解决方案 修改编译模式为正常Normal而非快速Fast …...
如何实现 C/C++ 与 Python 的通信?
在现代编程中,C/C与Python的通信已经成为一种趋势,尤其是在需要高性能和灵活性的场景中。本文将深入探讨如何实现这两者之间的互通,包括基础和高级方法,帮助大家在混合编程中游刃有余。 C/C 调用 Python(基础篇&#…...
音视频入门基础:FLV专题(13)——FFmpeg源码中,解析任意Type值的SCRIPTDATAVALUE类型的实现
一、SCRIPTDATAVALUE类型 从《音视频入门基础:FLV专题(9)——Script Tag简介》中可以知道,根据《video_file_format_spec_v10_1.pdf》第80到81页,SCRIPTDATAVALUE类型由一个8位(1字节)的Type和…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
