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

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

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

91. 解码方法

image-20231103192610042

题目解析

(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-1i-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];}
};

image-20231103194639683

总结

细节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];}
};

image-20231103195008881

相关文章:

[动态规划] (四) 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) 字符串非空&#xff0c;返回解码方法的总数 解题思路 状态表示 dp[i]&#xff1a;以i为结…...

Vue Vuex的使用和原理 专门解决共享数据的问题

Vuex专门解决共享数据的问题 多组件共享时使用&#xff0c;如用户ID各组件需要根据ID发送请求获取数据&#xff0c;任意组件可以进行增删改&#xff0c;相当于全局变量 Vuex 工作流程 如果确定值参数可以不经过Actions 直接走 安装Vuex vue2使用 vuex3 vue3使用 vuex4 npm i…...

第九周实验记录

1、安装Nerfstudio 环境配置 首先需要创建环境python3.8&#xff0c;接着需要安装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 微控制器中&#xff0c;FUS&#xff08;Firmware Upgrade Services&#xff09;是用于固件升级的一种服务。这项服务可以让你更新设备上的无…...

centos关闭Java进程的脚本

centos关闭Java进程的脚本&#xff0c;有时候服务就是个jar包&#xff0c;关闭程序又要找到进程ID&#xff0c;在kill掉&#xff0c;麻烦&#xff0c;这里就写了个脚本 小白教程&#xff0c;一看就会&#xff0c;一做就成。 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 面试时一道经典的面试问题&#xff0c;今天我们来聊一聊这个话题。 其实从名字上就能看出来个一二&#xff0c;BeanFactory 是 Factory 而 FactoryBean 是一个 Bean&#xff0c;我们先来看下总结&#xff1a; BeanFactory 是 Spring 框架的核心接口之一&#xf…...

黑马程序员项目-黑马点评

黑马点评1 短信登录 基于Session实现登录流程 发送验证码&#xff1a; 用户在提交手机号后&#xff0c;会校验手机号是否合法&#xff0c;如果不合法&#xff0c;则要求用户重新输入手机号 如果手机号合法&#xff0c;后台此时生成对应的验证码&#xff0c;同时将验证码进行…...

ubuntu 20.04 + Anaconda + cuda-11.8 + opencv-4.8.0(cuda)

环境&#xff1a;一键编译opencv-4.8.0(cuda)&#xff0c;前提是已经安装好了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语句&#xff0c;这是 Shell 独有的一种循环语句&#xff0c;非常适合终端&#xff08;Terminal&#xff09;这样的交互场景&#xff0c;它可以根据用户的设置显示出带编号的菜单&#xff0c;用户通过输入不同…...

线性回归与线性拟合的原理、推导与算法实现

关于回归和拟合&#xff0c;从它们的求解过程以及结果来看&#xff0c;两者似乎没有太大差别&#xff0c;事实也的确如此。从本质上说&#xff0c;回归属于数理统计问题&#xff0c;研究解释变量与响应变量之间的关系以及相关性等问题。而拟合是把平面的一系列点&#xff0c;用…...

【C++】set和multiset

文章目录 关联式容器键值对一、set介绍二、set的使用multiset 关联式容器 STL中的部分容器&#xff0c;比如&#xff1a;vector、list、deque、forward_list(C11)等&#xff0c;这些容器统称为序列式容器&#xff0c;因为其底层为线性序列的数据结构&#xff0c;里面存储的是元…...

二十、泛型(1)

本章概要 基本概念 与 C 的比较 简单泛型 一个元组类库一个堆栈类RandomList 基本概念 普通的类和方法只能使用特定的类型&#xff1a;基本数据类型或类类型。如果编写的代码需要应用于多种类型&#xff0c;这种严苛的限制对代码的束缚就会很大。 多态是一种面向对象思想的泛…...

【Unity数据交互】游戏中常用到的Json序列化

ˊˊ &#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1…...

TCP的滑动窗口和拥塞控制

目录 滑动窗口 1.发送窗口和接收窗口 2.滑动窗口的分类 停止等待协议&#xff1a;发送窗口大小 1&#xff0c; 接收窗口大小 1 后退N帧协议&#xff08;GBN&#xff09;&#xff1a;发送窗口大小 > 1&#xff0c;接收窗口大小 1 选择重传协议&#xff08;SR&#xf…...

零信任网络:一种全新的网络安全架构

随着网络技术的不断发展&#xff0c;网络安全问题日益凸显。传统的网络安全策略往往基于信任和验证&#xff0c;但这种信任策略存在一定的局限性。为了解决这一问题&#xff0c;零信任网络作为一种全新的网络安全架构&#xff0c;逐渐受到人们的关注。本文将对零信任网络的概念…...

基于单片机的智能拐杖软件设计

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 技术交流认准下方 CSDN 官方提供的联系方式 文章目录 概要 一、整体设计方案2.1本设计设计原理2.1.1单片机基本介绍 二、本设计方案选择三、软件设计AD原理图&#xff1a;原理图…...

小程序如何设置自动预约快递

小程序通过设置自动预约功能&#xff0c;可以实现自动将订单信息发送给快递公司&#xff0c;快递公司可以自动上门取件。下面具体介绍如何设置。 在小程序管理员后台->配送设置处&#xff0c;选择首选配送公司。为了能够支持自动预约快递&#xff0c;请选择正常的快递公司&…...

STM32-HAL库08-TIM的输出比较模式(输出PWM的另一种方式)

STM32-HAL库08-TIM的输出比较模式&#xff08;输出PWM的另一种方式&#xff09; 一、所用材料&#xff1a; STM32F103C6T6最小系统板 STM32CUBEMX&#xff08;HAL库软件&#xff09; MDK5 示波器或者逻辑分析仪 二、所学内容&#xff1a; 通过定时器TIM的输出比较模式得到预…...

告别B站评论区识人难题!这个免费工具让你一键掌握用户背景

告别B站评论区识人难题&#xff01;这个免费工具让你一键掌握用户背景 【免费下载链接】bilibili-comment-checker B站评论区自动标注成分&#xff0c;支持动态和关注识别以及手动输入 UID 识别 项目地址: https://gitcode.com/gh_mirrors/bil/bilibili-comment-checker …...

二相四线步进电机驱动全解析:从原理到Proteus仿真避坑指南

二相四线步进电机驱动全解析&#xff1a;从原理到Proteus仿真避坑指南 在工业自动化与嵌入式开发领域&#xff0c;步进电机因其精准的位置控制能力成为不可或缺的执行元件。而二相四线制步进电机凭借结构简单、成本低廉的优势&#xff0c;尤其受到电子工程师和创客群体的青睐。…...

STM32串口环形队列IAP固件更新方案

基于STM32串口环形队列的IAP实现方案1. 项目概述1.1 系统架构本方案实现了一种基于STM32F103C8T6微控制器的串口IAP(In-Application Programming)系统&#xff0c;采用环形队列缓冲机制解决有限SRAM空间下的固件更新问题。系统将64KB Flash空间划分为四个功能区域&#xff1a;B…...

为什么你的unipush消息收不到?详解个推通道状态检测与事件触发逻辑

为什么你的UniPush消息收不到&#xff1f;深度解析推送失效的7大关键因素 在移动应用开发中&#xff0c;消息推送是维系用户活跃度的核心功能之一。许多开发者在使用UniPush服务时&#xff0c;经常会遇到消息未能如期送达的困扰。本文将系统性地剖析消息推送失效的底层逻辑&…...

绿色低碳+高效交付:中集模块化数据中心用实力印证中国方案全球竞争力

随着人工智能与绿色转型成为全球经济增长核心引擎&#xff0c;高算力需求正推动数据中心建设向预制化、高效能方向加速演进。中集集团&#xff08;000039.SZ/2039.HK&#xff09;凭借工业化制造与全球交付优势&#xff0c;2025年在模块化数据中心&#xff08;AIDC&#xff09;领…...

【限时公开】20年农业AI工程师压箱底的17条精度校验铁律:从田间采集到模型上线零容错实践手册

第一章&#xff1a;农业图像识别精度校验的底层逻辑与行业特殊性农业图像识别并非通用计算机视觉任务的简单迁移&#xff0c;其精度校验需直面田间场景固有的复杂性&#xff1a;光照剧烈波动、作物生长阶段连续变化、病斑形态高度异质、背景杂草与土壤纹理干扰显著。这些因素共…...

梦幻动漫魔法工坊:5分钟零基础搭建,小白也能生成专属二次元头像

梦幻动漫魔法工坊&#xff1a;5分钟零基础搭建&#xff0c;小白也能生成专属二次元头像 想不想拥有一个独一无二的二次元头像&#xff0c;却苦于不会画画&#xff1f;或者想为你的游戏角色、小说人物创造一个生动的形象&#xff0c;却找不到合适的画师&#xff1f;今天&#x…...

NSC_BUILDER:Switch游戏文件管理的全能解决方案

NSC_BUILDER&#xff1a;Switch游戏文件管理的全能解决方案 【免费下载链接】NSC_BUILDER Nintendo Switch Cleaner and Builder. A batchfile, python and html script based in hacbuild and Nuts python libraries. Designed initially to erase titlerights encryption fro…...

ARM Neon加速NTT实战:如何在Cortex-A72上优化Kyber和Saber的加密性能

ARM Neon加速NTT实战&#xff1a;Cortex-A72上的Kyber与Saber性能优化 在移动安全领域&#xff0c;后量子密码算法的硬件加速已成为行业焦点。Cortex-A72作为ARM中端处理器的代表&#xff0c;其Neon指令集为NTT&#xff08;数论变换&#xff09;提供了显著的并行计算能力。本文…...

从“未知发布者”到“可信来源”:代码签名证书如何重塑用户信任?

一、用户信任危机&#xff1a;数字时代的核心挑战 在软件分发领域&#xff0c;"未知发布者"警告已成为开发者与用户之间的信任鸿沟。据2025年全球软件安全报告显示&#xff0c;73%的用户在看到此类警告时会直接放弃安装&#xff0c;即使软件来自知名企业。这种信任缺…...