力扣力扣力:91.解码方法
91. 解码方法 - 力扣(LeetCode)


在完成动态规划入门之后,我们先整一个中档题,也是前面简单题的变体。
分析思路:
在拿到最终结果之前,我们应该明确什么样的数字序列能够解码。
规则1:由于只有26个字母,所以如果是前后两位数字,必须要在1~26之间
规则2:单个0不能直接映射,例如03、05这种也不能映射,只有10和20才能够含有0
规则3:如果是单个映射那就只能在1~9之间,如果是两位数映射那么十位上只能是1或者2,如果是1的话,个位的范围是0~9,如果是2的话,个位的范围是0~6,也就是两位数在10~26之间
如果我们免去映射规则,那么这道题就退化成一次只能上一个或者两个台阶的题目了。所以这道题的区别就在于,有些台阶不能迈腿例如出现04,有些地方例如10或者20,只能迈两步不能迈一步,所以需要通过制定上面的规则来筛选出不能迈腿的地方,然后用台阶问题的模板解决。
接下里我们通过回答五个问题来逐步分析解题需要的过程。
1.状态表示什么
根据经验和题目要求,不难得到这道题的dp[i]可以表示为以i位置为结尾的解码方法的总数。我们一般先考虑从结尾向前,所以离结尾最近的一步有两种情况,据此写出状态转移方程。
2.状态转移方程
情况一:最后一步是单独解码,根据上面的规则可以知道,如果单独解码的数字在1~9之间则解码成功,否则解码失败不进行累加。
情况二:最后一步解码了两位数,根据上面的规则可以知道,如果两位数解码的数字在10~26之间则解码成功,否则解码失败不进行累加。
所以在两种情况都解码成功的情况下,状态转移方程为dp[i]=dp[i-1]+dp[i-2]

3.初始化
dp[0]:如果解码成功则为1,否则为0
dp[1]:情况一:单步和双步两种方法都解码失败,此时为0
情况二:单步和双步有一种成功一种失败,此时为1
情况三:单步和双步都解码成功,此时为2
4.填表顺序
根据状态转移方程可以知道:后面的值依赖前面的值,所以是从前往后填
5.返回值
按照dp[i]的定义可以知道,最后返回的就是dp[n-1]
具体实现:
class Solution {
public:int numDecodings(string s) {int n = s.size();vector<int> dp(n);//初始化dp[0] = (s[0] != '0');//先处理边界情况if(n == 1) return dp[0];//如果前两个数都不为0,就说明能单步解码if(s[0] != '0' && s[1] != '0')dp[1] += 1;int num = (s[0] - '0') *10 + s[1] -'0';//通过ASCII码转化来保存前两个位表示的数if(num>=10 && num<=26)dp[1] += 1;//填表for(int i=2;i<n;i++){if(s[i] != '0')dp[i] += dp[i-1];int tmp = (s[i-1] - '0')* 10 + s[i] - '0';//保存这种情况代表的两位数if(tmp>=10 && tmp<=26)dp[i] += dp[i-2];} return dp[n-1];}
};相关文章:
力扣力扣力:91.解码方法
91. 解码方法 - 力扣(LeetCode) 在完成动态规划入门之后,我们先整一个中档题,也是前面简单题的变体。 分析思路: 在拿到最终结果之前,我们应该明确什么样的数字序列能够解码。 规则1:由于只有…...
一些面试题总结(二)
21、TCP的四次挥手? 在断开TCP连接时,需要通过四次挥手来断开,过程是: (1)客户端向服务端发送FIN1和序列号SEQx的数据包,用来关闭客户端到服务端的数据传送。然后客户端进入 FIN-WAIT-1 状态。 (2)服务端接收FIN后,…...
Hive-testbench套件使用文档
Hive-testbench套件使用文档 hive-testbench 是hortonworks的一个开源项目,用于测试和基准测试 Apache Hive 的工具集。它提供了一系列的测试数据集和查询样例,用于评估和比较 Hive 在不同配置和环境下的性能。hive-testbench 的主要目标是模拟真实的大规模数据集和复杂查询…...
大数据新视界 -- 大数据大厂之 Impala 性能优化:新技术融合的无限可能(下)(12/30)
💖💖💖亲爱的朋友们,热烈欢迎你们来到 青云交的博客!能与你们在此邂逅,我满心欢喜,深感无比荣幸。在这个瞬息万变的时代,我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…...
Python | Leetcode Python题解之第540题有序数组中的单一元素
题目: 题解: class Solution:def singleNonDuplicate(self, nums: List[int]) -> int:low, high 0, len(nums) - 1while low < high:mid (low high) // 2mid - mid & 1if nums[mid] nums[mid 1]:low mid 2else:high midreturn nums[l…...
AHB Matrix 四星级 验证笔记(2.4) Tt3.3AHB总线协议测试时的 并行数据
文章目录 前言一、代码二、错误1.地址范围2. 并行执行线程中变量覆盖的情况3.有关incr的beat 前言 来源路科验证本节搞定 T3.3 AHB总线协议的覆盖:AHB_PROTOCOL_COVER 即测试ahb slave接口和master接口支持(尽可能)全部的ahb协议传输场景&am…...
前端零基础学习Day-Eight
CSS字体和文本样式 CSS文字样式 字体:font-family 语法:font-family:[字体1][,字体2][,...] p{font-family:"微软雅黑","宋体","黑体";} 含空格字体名和中文,用英文引号括起 属性值:具体字体名&…...
贪心算法day3(最长递增序列问题)
目录 1.最长递增三元子序列 2.最长连续递增序列 1.最长递增三元子序列 题目链接:. - 力扣(LeetCode) 思路:我们只需要设置两个数进行比较就好。设a为nums[0],b 为一个无穷大的数,只要有比a小的数字就赋值…...
【论文复现】MSA+抑郁症模型总结(三)
📝个人主页🌹:Eternity._ 🌹🌹期待您的关注 🌹🌹 ❀MSA抑郁症模型 热门研究领域:情感计算的横向发展1. 概述2. 论文地址3. 研究背景4. 主要贡献5. 模型结构和代码6. 数据集介绍7. 性…...
【软件测试】敏捷模型(Scrum模型)和V模型、W模型
敏捷模型 前面的那些模型以前非常流行,但现在开发人员在使用的时候会遇到各种问题。主要困难包括在项目开发期间处理来自客户的变更请求,以及合并这些变更所需要的高成本和时间。 在实际工作中,一款产品的功能是不断在变化的 所以为了克服这…...
【go从零单排】接口(interface)和多态(Polymorphism)
🌈Don’t worry , just coding! 内耗与overthinking只会削弱你的精力,虚度你的光阴,每天迈出一小步,回头时发现已经走了很远。 📗概念 在Go语言中,interface 是一种重要的类型,用于定义一组方法…...
SI5319C-C-GM,SiliconLabs芯科 SI5319C-C-GMR,时钟合成器/抖动清除器 封装 QFN-36 在售 20000PCS 23+
SI5319C-C-GM是SiliconLabs公司生产的时钟合成器和抖动清除器。它是一款高性能的时钟解决方案,可用于各种应用领域,包括通信、数据中心、消费电子等。 该器件采用了SiliconLabs独有的DSPLL技术,能够提供低抖动和高精度的时钟信号。它具有多个…...
使用批处理脚本批量删除Maven无效依赖
背景 在开发过程中,我们经常会遇到以下情况: 在pom.xml文件中错误地指定了依赖的名称。因为网络问题,某些依赖下载不完全。依赖版本号错误,导致下载的文件无法使用。 这些情况会导致Maven在本地仓库中留下一些无效的文件&#…...
腾讯cos对象存储,下行流量费贵,是否可以加入服务器减少费用,架构如何设计
腾讯云COS(Cloud Object Storage)对象存储服务提供了一种高效、安全、低成本的方式存储大量数据。然而,当涉及到外网下行流量时,确实会产生一定的费用,这可能会增加整体的成本。为了减少这些费用,可以通过以…...
【SAP】关于权限的继承
关于权限的父role和子role的权限继承,既可以 从子role主动去父role那里“取”。从父role“推”到子role 我自己之前一直用的是方法1,但由于子role很多,一个一个手工维护花了不少时间。 后来得知有方法2,特此测试。 我准备了父R…...
SpringBoot技术下的共享汽车运营平台
1系统概述 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及,互联网成为人们查找信息的重要场所,二十一世纪是信息的时代,所以信息的管理显得特别重要。因此,使用计算机来管理共享汽车管理系统的相关信息成为必然。开发…...
SwiftUI开发教程系列 - 第7章:数据流和状态管理
SwiftUI 的核心优势之一在于其声明式的数据绑定和状态管理系统,使得在多视图间传递和更新数据变得更加直观和高效。在本章中,我们将讨论如何使用 ObservedObject、EnvironmentObject、StateObject 等属性包装器进行复杂的数据管理,确保应用的…...
Ubuntu系统安装NVIDIA驱动、CUDA、PyTorch等GPU深度学习环境
学习目标: 在Ubuntu系统上安装CUDA、PyTorch等GPU深度学习环境,主要目标是为深入研究深度学习和深度强化学习提供高效的计算支持。通过构建GPU环境,计划掌握深度学习的基本概念和算法应用,提高模型训练效率,特别是在复…...
电子学会2024年3月青少年软件编程(图形化)等级考试试卷(三级)真题,含答案解析
我们今天分享的资料是:电子学会2024年3月青少年软件编程(图形化)等级考试试卷(三级)真题,含答案解析 电子学会 2024 年 3 月青少年软件编程(图形化)等级三级考试的主要考点包括但不限于以下内容: 理解变量的概念:能够新建变量,知道如何在舞台区显示或隐藏变量,理解…...
初学者指南:用例图——开启您的软件工程之旅
目录 背景: 基本组成: 关联(Assciation): 包含(Include): 扩展(Extend): 泛化(Inheritance): 完整银行…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
wpf在image控件上快速显示内存图像
wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像(比如分辨率3000*3000的图像)的办法,尤其是想把内存中的裸数据(只有图像的数据,不包…...
