[动态规划] (四) LeetCode 91.解码方法
[动态规划] (四) LeetCode 91.解码方法
91. 解码方法

题目解析
(1) 对字母A - Z进行编码1-26
(2)11106可以解码为1-1-10-6或者11-10-6, 但是11-1-06不能解码
(3) 0n不能解码
(4) 字符串非空,返回解码方法的总数
解题思路
状态表示
dp[i]:以i为结尾,的解码方法
状态转移方程
1.单独解码
- dp[i]与dp[i-1]分别解码:s[i]解码成功,即加上dp[i-1];解码失败,则这种方法以及之前的解码方法dp[i-1]是错误的,方法数0
2.组合解码
- dp[i]与dp[i-1]组合:s[i-1] * 10 + s[i],解码成功,即加上dp[i-2];解码失败,则到dp[i-2]的方法是错误的,方法数0
初始化和填表顺序
- 初始化
我们使用了i-1和i-2的值,所以初始化dp[0]和dp[1]。
dp[0]与s[0]有关
dp[1]与s[1]有关,还与s[0]与s[1]的组合有关
dp[0] = s[0] != '0';
if(dp[1] != '0') dp += dp[0];
if(dp[0] != '0' && dp[1] != '0') dp[1] += dp[0];
int sum = ((dp[0] - '0') * 10 + (dp[1] - '0'));
if(sum >= 10 && sum <= 26) dp[1] += 1;
- 填表顺序
从左往右填表
返回值
返回n-1位置即可,同状态表示
代码实现
class Solution {
public:int numDecodings(string s) {//构建dp数组int n = s.size();vector<int> dp(n);//初始化if(s[0] != '0') dp[0] = 1;//单独解码if(n == 1) return dp[0];if(s[0] != '0' && s[1] != '0') dp[1] += dp[0];//单独解码int sum = (s[0] - '0') * 10 + s[1] - '0';if(sum >= 10 && sum <= 26) dp[1]++;//组合解码//填表for(int i = 2; i < n; i++){//情况1if(s[i] != '0') dp[i] += dp[i-1];//情况2sum = (s[i-1] - '0') * 10 + s[i] - '0';if(sum >= 10 && sum <= 26) dp[i] += dp[i-2];}//返回结果return dp[n-1];}
};

总结
细节1:字符串中数字进行±*/需要减一个字符0。
细节2:数据范围,字符串长度为1时直接返回dp[0]
细节3:初始化dp[1]时的代码与填表时的代码高度重合,我们可以进行优化
优化方法
1.将申请的空间扩大一位,将填表的下标向后推一位。
2.dp[0]初始化为1,dp[0]为我们虚构出来的一位;因为我们想要使i=2,dp[i]初始化正确,会访问到dp[i-2]。如果dp[0]为0,在计算组合的情况时,就会少加一次dp[i-2]。
3.因为我们把申请的空间dp,填表下标向后推一位,访问字符串s的下标得前进一位,则循环中s[i]的i都得减1。
4.将填表的下标向后推一位,返回值也得向后推一位,即dp[n]。
优化代码
class Solution {
public:int numDecodings(string s) {//优化代码int n = s.size();vector<int> dp(n+1);dp[0] = 1;dp[1] = s[0] != '0';if(n == 1) return dp[1];for(int i = 2; i <= n; i++){if(s[i-1] != '0') dp[i] += dp[i-1];int sum = ((s[i-2] - '0') * 10) + (s[i-1] - '0');if(sum >= 10 && sum <= 26) dp[i] += dp[i-2];}return dp[n];}
};

相关文章:
[动态规划] (四) LeetCode 91.解码方法
[动态规划] (四) LeetCode 91.解码方法 91. 解码方法 题目解析 (1) 对字母A - Z进行编码1-26 (2)11106可以解码为1-1-10-6或者11-10-6, 但是11-1-06不能解码 (3) 0n不能解码 (4) 字符串非空,返回解码方法的总数 解题思路 状态表示 dp[i]:以i为结…...
Vue Vuex的使用和原理 专门解决共享数据的问题
Vuex专门解决共享数据的问题 多组件共享时使用,如用户ID各组件需要根据ID发送请求获取数据,任意组件可以进行增删改,相当于全局变量 Vuex 工作流程 如果确定值参数可以不经过Actions 直接走 安装Vuex vue2使用 vuex3 vue3使用 vuex4 npm i…...
第九周实验记录
1、安装Nerfstudio 环境配置 首先需要创建环境python3.8,接着需要安装cuda11.7或11.3 这里安装cuda11.7 pip uninstall torch torchvision functorchpip install torch1.13.1 torchvision functorch --extra-index-url https://download.pytorch.org/whl/cu117安…...
STM32WB55开发(6)----FUS更新
STM32WB55开发.6--FUS更新 概述视频教学硬件准备存储器映射FLASH安全区设置SRAM安全区设置通过USB进行下载注意事项 概述 在 STM32WB 微控制器中,FUS(Firmware Upgrade Services)是用于固件升级的一种服务。这项服务可以让你更新设备上的无…...
centos关闭Java进程的脚本
centos关闭Java进程的脚本,有时候服务就是个jar包,关闭程序又要找到进程ID,在kill掉,麻烦,这里就写了个脚本 小白教程,一看就会,一做就成。 1.脚本如下 #!/bin/bash ps -ef | grep java | gre…...
深度学习网络模型 MobileNet系列MobileNet V1、MobileNet V2、MobileNet V3网络详解以及pytorch代码复现
深度学习网络模型 MobileNet系列MobileNet V1、MobileNet V2、MobileNet V3网络详解以及pytorch代码复现 1、DW卷积与普通卷积计算量对比DW与PW计算量普通卷积计算量计算量对比 2、MobileNet V1MobileNet V1网络结构MobileNet V1网络结构代码 3、MobileNet V2倒残差结构模块倒残…...
Spring 中 BeanFactory 和 FactoryBean 有何区别?
这也是 Spring 面试时一道经典的面试问题,今天我们来聊一聊这个话题。 其实从名字上就能看出来个一二,BeanFactory 是 Factory 而 FactoryBean 是一个 Bean,我们先来看下总结: BeanFactory 是 Spring 框架的核心接口之一…...
黑马程序员项目-黑马点评
黑马点评1 短信登录 基于Session实现登录流程 发送验证码: 用户在提交手机号后,会校验手机号是否合法,如果不合法,则要求用户重新输入手机号 如果手机号合法,后台此时生成对应的验证码,同时将验证码进行…...
ubuntu 20.04 + Anaconda + cuda-11.8 + opencv-4.8.0(cuda)
环境:一键编译opencv-4.8.0(cuda),前提是已经安装好了cuda和cudnn Anaconda安装 参考: https://blog.csdn.net/weixin_46947765/article/details/130980957 opencv4.8.0编译安装 一键编译shell脚本 VERSION4.8.0test -e ${VERSION}.zip || wget http…...
Linux 目录
目录 1. Linux 目录1.1. 目录 /usr/bin 和 /usr/local/bin 区别 1. Linux 目录 1.1. 目录 /usr/bin 和 /usr/local/bin 区别 /usr/bin 下面的都是系统预装的可执行程序, 系统升级有可能会被覆盖。/usr/local/bin 目录是给用户放置自己的可执行程序。...
Linux shell编程学习笔记21:用select in循环语句打造菜单
一、select in循环语句的功能 Linux shell脚本编程提供了select in语句,这是 Shell 独有的一种循环语句,非常适合终端(Terminal)这样的交互场景,它可以根据用户的设置显示出带编号的菜单,用户通过输入不同…...
线性回归与线性拟合的原理、推导与算法实现
关于回归和拟合,从它们的求解过程以及结果来看,两者似乎没有太大差别,事实也的确如此。从本质上说,回归属于数理统计问题,研究解释变量与响应变量之间的关系以及相关性等问题。而拟合是把平面的一系列点,用…...
【C++】set和multiset
文章目录 关联式容器键值对一、set介绍二、set的使用multiset 关联式容器 STL中的部分容器,比如:vector、list、deque、forward_list(C11)等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元…...
二十、泛型(1)
本章概要 基本概念 与 C 的比较 简单泛型 一个元组类库一个堆栈类RandomList 基本概念 普通的类和方法只能使用特定的类型:基本数据类型或类类型。如果编写的代码需要应用于多种类型,这种严苛的限制对代码的束缚就会很大。 多态是一种面向对象思想的泛…...
【Unity数据交互】游戏中常用到的Json序列化
ˊˊ 👨💻个人主页:元宇宙-秩沅 👨💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨💻 本文由 秩沅 原创 👨💻 收录于专栏࿱…...
TCP的滑动窗口和拥塞控制
目录 滑动窗口 1.发送窗口和接收窗口 2.滑动窗口的分类 停止等待协议:发送窗口大小 1, 接收窗口大小 1 后退N帧协议(GBN):发送窗口大小 > 1,接收窗口大小 1 选择重传协议(SR…...
零信任网络:一种全新的网络安全架构
随着网络技术的不断发展,网络安全问题日益凸显。传统的网络安全策略往往基于信任和验证,但这种信任策略存在一定的局限性。为了解决这一问题,零信任网络作为一种全新的网络安全架构,逐渐受到人们的关注。本文将对零信任网络的概念…...
基于单片机的智能拐杖软件设计
欢迎大家点赞、收藏、关注、评论啦 ,由于篇幅有限,只展示了部分核心代码。 技术交流认准下方 CSDN 官方提供的联系方式 文章目录 概要 一、整体设计方案2.1本设计设计原理2.1.1单片机基本介绍 二、本设计方案选择三、软件设计AD原理图:原理图…...
小程序如何设置自动预约快递
小程序通过设置自动预约功能,可以实现自动将订单信息发送给快递公司,快递公司可以自动上门取件。下面具体介绍如何设置。 在小程序管理员后台->配送设置处,选择首选配送公司。为了能够支持自动预约快递,请选择正常的快递公司&…...
STM32-HAL库08-TIM的输出比较模式(输出PWM的另一种方式)
STM32-HAL库08-TIM的输出比较模式(输出PWM的另一种方式) 一、所用材料: STM32F103C6T6最小系统板 STM32CUBEMX(HAL库软件) MDK5 示波器或者逻辑分析仪 二、所学内容: 通过定时器TIM的输出比较模式得到预…...
流式清洗新标准:Polars 2.0 Streaming ETL在Kafka-ClickHouse链路中的低延迟落地(端到端<120ms)
第一章:流式清洗新标准:Polars 2.0 Streaming ETL在Kafka-ClickHouse链路中的低延迟落地(端到端<120ms) Polars 2.0 引入的原生流式执行引擎(Streaming Execution Engine)彻底重构了传统批式DataFrame处…...
LeetDown完全指南:系统降级功能解决A6/A7设备用户的卡顿痛点
LeetDown完全指南:系统降级功能解决A6/A7设备用户的卡顿痛点 【免费下载链接】LeetDown a GUI macOS Downgrade Tool for A6 and A7 iDevices 项目地址: https://gitcode.com/gh_mirrors/le/LeetDown LeetDown是一款专为macOS设计的图形化降级工具࿰…...
iOS激活锁绕过终极指南:快速解锁iPhone/iPad的完整解决方案
iOS激活锁绕过终极指南:快速解锁iPhone/iPad的完整解决方案 【免费下载链接】applera1n icloud bypass for ios 15-16 项目地址: https://gitcode.com/gh_mirrors/ap/applera1n 当你面对一部显示"激活锁"界面的iOS设备,反复输入Apple I…...
别再让AI瞎忙活了!用Claude Code的SubAgent打造你的专属开发团队(附React项目实战)
别再让AI瞎忙活了!用Claude Code的SubAgent打造你的专属开发团队(附React项目实战) 在软件开发的世界里,我们常常面临一个困境:要么雇佣一个庞大的团队,每个成员各司其职但成本高昂;要么依赖全能…...
QQ音乐下载的歌曲怎么导出来?分享我的FFMpeg自动化处理脚本(附Win/Mac命令)
用FFMpeg实现QQ音乐文件自动化处理:跨平台脚本全解析 每次从QQ音乐下载的歌曲文件总是带着各种限制——加密格式只能在特定播放器打开,专辑封面无法显示,批量处理更是让人头疼。作为一个整理过上千首音乐文件的资深用户,我摸索出…...
你的加密音乐文件,是否真的属于你?
你的加密音乐文件,是否真的属于你? 【免费下载链接】unlock-music 在浏览器中解锁加密的音乐文件。原仓库: 1. https://github.com/unlock-music/unlock-music ;2. https://git.unlock-music.dev/um/web 项目地址: https://gitc…...
手指划过屏幕放大模型界面,环氧树脂层和纤维基体在激光路径下呈现出清晰的物理场分布。突然发现这个双层材料烧蚀模型跑得格外顺畅——看来前几天通宵调参没白费
comsol激光清洗、烧蚀双层材料 表面一层50μm厚度的环氧树脂(可更换成其他材料),基体材料为纤维材料。 添加功率为13W的激光进行清洗或烧蚀 模型非常成功、角度选择很奈斯在COMSOL里建模时有个小细节特别关键:把环氧树脂层的厚度参数设为全局变量。别小看…...
NaViL-9B图文问答入门:Web界面支持拖拽上传+历史记录回溯功能
NaViL-9B图文问答入门:Web界面支持拖拽上传历史记录回溯功能 1. 平台介绍 NaViL-9B是一款原生多模态大语言模型,由专业研究机构开发。它不仅能像传统语言模型一样处理纯文本问答,还具备强大的图片理解能力。这意味着你可以上传一张图片&…...
8_Harness驾驭工程实践:企业级落地与OpenAI案例解析
8_Harness驾驭工程实践:企业级落地与OpenAI案例解析 关键字: 企业级落地、OpenAI、Ryan Lopopolo、Codex、Harness Engineering、Citi Bank、Ancestry、Ulta Beauty、Agent-First开发、部署策略、自托管、成本优化、迁移路径、最佳实践、0行手写代码、百…...
每日股票分析自动化:基于Ollama的daily_stock_analysis镜像实战教程
每日股票分析自动化:基于Ollama的daily_stock_analysis镜像实战教程 1. 为什么需要本地化AI股票分析工具 在金融投资领域,及时获取准确的股票分析至关重要。传统方式需要人工收集数据、分析图表、撰写报告,整个过程耗时耗力。而基于大语言模…...
