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

力扣力扣力: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. 解码方法 - 力扣&#xff08;LeetCode&#xff09; 在完成动态规划入门之后&#xff0c;我们先整一个中档题&#xff0c;也是前面简单题的变体。 分析思路&#xff1a; 在拿到最终结果之前&#xff0c;我们应该明确什么样的数字序列能够解码。 规则1&#xff1a;由于只有…...

一些面试题总结(二)

21、TCP的四次挥手? 在断开TCP连接时&#xff0c;需要通过四次挥手来断开&#xff0c;过程是&#xff1a; (1)客户端向服务端发送FIN1和序列号SEQx的数据包&#xff0c;用来关闭客户端到服务端的数据传送。然后客户端进入 FIN-WAIT-1 状态。 (2)服务端接收FIN后&#xff0c;…...

Hive-testbench套件使用文档

Hive-testbench套件使用文档 hive-testbench 是hortonworks的一个开源项目,用于测试和基准测试 Apache Hive 的工具集。它提供了一系列的测试数据集和查询样例,用于评估和比较 Hive 在不同配置和环境下的性能。hive-testbench 的主要目标是模拟真实的大规模数据集和复杂查询…...

大数据新视界 -- 大数据大厂之 Impala 性能优化:新技术融合的无限可能(下)(12/30)

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…...

Python | Leetcode Python题解之第540题有序数组中的单一元素

题目&#xff1a; 题解&#xff1a; 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总线协议的覆盖&#xff1a;AHB_PROTOCOL_COVER 即测试ahb slave接口和master接口支持&#xff08;尽可能&#xff09;全部的ahb协议传输场景&am…...

前端零基础学习Day-Eight

CSS字体和文本样式 CSS文字样式 字体&#xff1a;font-family 语法&#xff1a;font-family:[字体1][,字体2][,...] p{font-family:"微软雅黑","宋体","黑体";} 含空格字体名和中文&#xff0c;用英文引号括起 属性值&#xff1a;具体字体名&…...

贪心算法day3(最长递增序列问题)

目录 1.最长递增三元子序列 2.最长连续递增序列 1.最长递增三元子序列 题目链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a;我们只需要设置两个数进行比较就好。设a为nums[0]&#xff0c;b 为一个无穷大的数&#xff0c;只要有比a小的数字就赋值…...

【论文复现】MSA+抑郁症模型总结(三)

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; ❀MSA抑郁症模型 热门研究领域&#xff1a;情感计算的横向发展1. 概述2. 论文地址3. 研究背景4. 主要贡献5. 模型结构和代码6. 数据集介绍7. 性…...

【软件测试】敏捷模型(Scrum模型)和V模型、W模型

敏捷模型 前面的那些模型以前非常流行&#xff0c;但现在开发人员在使用的时候会遇到各种问题。主要困难包括在项目开发期间处理来自客户的变更请求&#xff0c;以及合并这些变更所需要的高成本和时间。 在实际工作中&#xff0c;一款产品的功能是不断在变化的 所以为了克服这…...

【go从零单排】接口(interface)和多态(Polymorphism)

&#x1f308;Don’t worry , just coding! 内耗与overthinking只会削弱你的精力&#xff0c;虚度你的光阴&#xff0c;每天迈出一小步&#xff0c;回头时发现已经走了很远。 &#x1f4d7;概念 在Go语言中&#xff0c;interface 是一种重要的类型&#xff0c;用于定义一组方法…...

SI5319C-C-GM,SiliconLabs芯科 SI5319C-C-GMR,时钟合成器/抖动清除器 封装 QFN-36 在售 20000PCS 23+

SI5319C-C-GM是SiliconLabs公司生产的时钟合成器和抖动清除器。它是一款高性能的时钟解决方案&#xff0c;可用于各种应用领域&#xff0c;包括通信、数据中心、消费电子等。 该器件采用了SiliconLabs独有的DSPLL技术&#xff0c;能够提供低抖动和高精度的时钟信号。它具有多个…...

使用批处理脚本批量删除Maven无效依赖

背景 在开发过程中&#xff0c;我们经常会遇到以下情况&#xff1a; 在pom.xml文件中错误地指定了依赖的名称。因为网络问题&#xff0c;某些依赖下载不完全。依赖版本号错误&#xff0c;导致下载的文件无法使用。 这些情况会导致Maven在本地仓库中留下一些无效的文件&#…...

腾讯cos对象存储,下行流量费贵,是否可以加入服务器减少费用,架构如何设计

腾讯云COS&#xff08;Cloud Object Storage&#xff09;对象存储服务提供了一种高效、安全、低成本的方式存储大量数据。然而&#xff0c;当涉及到外网下行流量时&#xff0c;确实会产生一定的费用&#xff0c;这可能会增加整体的成本。为了减少这些费用&#xff0c;可以通过以…...

【SAP】关于权限的继承

关于权限的父role和子role的权限继承&#xff0c;既可以 从子role主动去父role那里“取”。从父role“推”到子role 我自己之前一直用的是方法1&#xff0c;但由于子role很多&#xff0c;一个一个手工维护花了不少时间。 后来得知有方法2&#xff0c;特此测试。 我准备了父R…...

SpringBoot技术下的共享汽车运营平台

1系统概述 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及&#xff0c;互联网成为人们查找信息的重要场所&#xff0c;二十一世纪是信息的时代&#xff0c;所以信息的管理显得特别重要。因此&#xff0c;使用计算机来管理共享汽车管理系统的相关信息成为必然。开发…...

SwiftUI开发教程系列 - 第7章:数据流和状态管理

SwiftUI 的核心优势之一在于其声明式的数据绑定和状态管理系统&#xff0c;使得在多视图间传递和更新数据变得更加直观和高效。在本章中&#xff0c;我们将讨论如何使用 ObservedObject、EnvironmentObject、StateObject 等属性包装器进行复杂的数据管理&#xff0c;确保应用的…...

Ubuntu系统安装NVIDIA驱动、CUDA、PyTorch等GPU深度学习环境

学习目标&#xff1a; 在Ubuntu系统上安装CUDA、PyTorch等GPU深度学习环境&#xff0c;主要目标是为深入研究深度学习和深度强化学习提供高效的计算支持。通过构建GPU环境&#xff0c;计划掌握深度学习的基本概念和算法应用&#xff0c;提高模型训练效率&#xff0c;特别是在复…...

电子学会2024年3月青少年软件编程(图形化)等级考试试卷(三级)真题,含答案解析

我们今天分享的资料是:电子学会2024年3月青少年软件编程(图形化)等级考试试卷(三级)真题,含答案解析 电子学会 2024 年 3 月青少年软件编程(图形化)等级三级考试的主要考点包括但不限于以下内容: 理解变量的概念:能够新建变量,知道如何在舞台区显示或隐藏变量,理解…...

初学者指南:用例图——开启您的软件工程之旅

目录 背景&#xff1a; 基本组成&#xff1a; 关联&#xff08;Assciation&#xff09;&#xff1a; 包含&#xff08;Include&#xff09;&#xff1a; 扩展&#xff08;Extend&#xff09;&#xff1a; 泛化&#xff08;Inheritance&#xff09;&#xff1a; 完整银行…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...