91. 解码方法 -dp4

. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/decode-ways/description/

示例 1:

输入:s = "12"
输出:2
解释:它可以解码为 "AB"(1 2)或者 "L"(12)。

示例 2:

输入:s = "226"
输出:3
解释:它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3:

输入:s = "06"
输出:0
解释:"06" 无法映射到 "F" ,因为存在前导零("6" 和 "06" 并不等价)。

60也无法成功解码。

 

class Solution {
public:int numDecodings(string s) {int n=s.size();vector<int> dp(n);if(s[0]=='0') return 0;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];}return dp[n-1];}
};

优化:

class Solution {
public:int numDecodings(string s) {int n=s.size();vector<int> dp(n+1);dp[0]=1;dp[1]=s[1-1]!='0';for(int i=2;i<=n;i++){if(s[i-1]!='0') dp[i]+=dp[i-1];int t = (s[i-2]-'0')*10+(s[i-1]-'0');if(t>=10&&t<=26) dp[i]+=dp[i-2];}return dp[n];}
};

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/405174.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

「字符串」前缀函数|KMP匹配:规范化next数组 / LeetCode 28(C++)

概述 为什么大家总觉得KMP难&#xff1f;难的根本就不是这个算法本身。 在互联网上你可以见到八十种KMP算法的next数组定义和模式串回滚策略&#xff0c;把一切都懂得特别混乱。很多时候初学者的难点根本不在于这个算法本身&#xff0c;而是它令人痛苦的百花齐放的定义。 有…

ee trade:黄金投资与股票投资的区别

黄金和股票&#xff0c; 是金融市场中两种常见的投资工具&#xff0c; 它们拥有截然不同的特点和风险&#xff0c; 了解它们的差异&#xff0c; 可以帮助投资者制定更合理的投资策略。 一、 投资性质&#xff1a; 避险与成长&#xff0c; 两种投资方向 黄金&#xff1a; 被视…

【C++】入门篇一

【C】入门篇一 一 .缺省参数1.缺省参数的概念2. 缺省参数分类 二. 函数重载1. 函数重载概念2.函数重载代码举例 三.引用1.引用的概念2. 引用特性3. 常引用4. 使用场景(1). 做参数(2). 做返回值 5. 传值、传引用效率比较6. 引用和指针的区别7.引用和指针的不同点 一 .缺省参数 …

如何将MySQL迁移到TiDB,完成无缝业务切换?

当 MySQL 数据库的单表数据量达到了亿级&#xff0c;会发生什么&#xff1f; 这个现象表示公司的业务上了一个台阶&#xff0c;随着数据量的增加&#xff0c;公司规模也进一步扩大了&#xff0c;是非常喜人的一个改变 &#xff0c;然而随之而来的其他变化&#xff0c;就没那么…

Python | Leetcode Python题解之第354题俄罗斯套娃信封问题

题目&#xff1a; 题解&#xff1a; class Solution:def maxEnvelopes(self, envelopes: List[List[int]]) -> int:if not envelopes:return 0n len(envelopes)envelopes.sort(keylambda x: (x[0], -x[1]))f [1] * nfor i in range(n):for j in range(i):if envelopes[j]…

全液冷服务器革命:CPU、内存、PCIe高效散热新方案

在国家十四五规划大力发展数字经济的背景下&#xff0c;数据中心作为算力的核心载体&#xff0c;其基础设施成为支撑数字经济的“数字底座”&#xff0c;但同时也面临巨大的碳排放压力。随着芯片与服务器功耗的上升&#xff0c;单机柜功率密度不断增大&#xff0c;传统风冷散热…

深度学习设计模式之享元设计模式

文章目录 前言一、介绍二、特点三、详细介绍1.核心组成2.代码示例3.优缺点优点缺点 4.使用场景 总结 前言 享元设计模式主要用于减少创建对象的数量&#xff0c;以减少内存占用&#xff0c;提高性能。 一、介绍 享元设计模式&#xff08;Flyweight Pattern&#xff09;是一种…

Hexo通过GitHub设置自定义域名

本身GitHub也是支持自定义域名的&#xff0c;本次教程将讲解如何使用GitHub自带的自定义域名解析。 1. GitHub设置 1.1 登录GitHub账号 登录GitHub账号&#xff0c;找到名称为 用户名.github.io的仓库&#xff0c;并点击进入。 1.2 进入Settings页面 点击如图的Settings按…

【体检】程序人生之健康检查,全身体检与预防疫苗,五大传染病普筛,基因检测等

程序员养生指南之 【体检】程序人生之健康检查&#xff0c;全身体检项目分类&#xff0c;五大传染病普筛&#xff0c;基因检测等 文章目录 一、全身体检与预防疫苗&#xff08;年检&#xff09;1、实验室检测&#xff1a;生化全套检查2、医技检查&#xff1a;辅助诊疗科室3、科…

python中使用gurobi遇到强不等式约束(只有大于或者小于而不是大于等于或者小于等于的形式)的解决办法

文章目录 情况分析与解决思路数学模型严格不等式约束转化后的约束形式带入具体的 ϵ \epsilon ϵ 值 python代码总结 情况分析与解决思路 在gurobi求解数学优化问题时&#xff0c;标准的约束形式通常是大于等于&#xff08; >&#xff09;或小于等于&#xff08;<&…

Linux:网络基础概念

网络发展 独立模式: 计算机之间相互独立; 网络互联: 多台计算机连接在一起, 完成数据共享; 局域网 LAN: 计算机数量更多了, 通过交换机和路由器连接在一起; 广域网 WAN: 将远隔千里的计算机都连在一起; 所谓 "局域网" 和 "广域网" 只是一个相对的概念. 比如…

如何使用DEV-C++做游戏?

我的B站视频做过关于python的小游戏开发&#xff0c;但很多小伙伴希望通过C做一些有趣的动画或游戏&#xff0c;该怎么实现呢&#xff1f; B站&#xff1a;bigbigli_大李 大家好&#xff0c;我是大李。 今天主要跟大家谈谈如何通过C做一些小游戏开发&#xff0c;这里我们就 使用…

【游戏】什么是摄影游戏(Photography Games)

“Photography games” 是指以摄影为主题或核心机制的电子游戏。这类游戏通常让玩家通过虚拟摄像头或相机捕捉游戏世界中的场景、人物、动物或物品。这些游戏可以有不同的玩法和目标&#xff0c;通常包括以下几种类型&#xff1a; 探索与拍摄&#xff1a;玩家在游戏世界中自由…

嵌入式学习Day36---Linux软件编程---网络编程

目录 一、TCP并发模型 1.1.阻塞IO 1.2.非阻塞IO 1.步骤 2.函数接口 3.实例 1.3.异步IO 1.步骤 2.函数接口 3.实例 1.4.多路复用IO 1.select 函数接口&#xff1a; 实例 2.poll 3.epoll 二、总结 一、TCP并发模型 1.1.阻塞IO CPU占用率低,等待资源时将任务挂…

如何查看Squid的DNS缓存

使用squidclient mgr:ipcache命令查看Squid的DNS缓存记录 如果squid端口不是3128, 需要指定端口号, squidclient -p {port} mgr:ipcache # squidclient mgr:ipcache ... IP Cache Statistics: ... IP Cache Contents:Hostname Flg lstref TTL N(b)…

【旭日x3派】部署官方yolov5全流程

地平线旭日x3派部署yolov5--全流程 前言一、深度学习环境安装二、安装docker三、部署3.1、安装工具链镜像3.2、配置天工开物OpenExplorer工具包3.3、创建深度学习虚拟空间&#xff0c;安装依赖&#xff1a;3.4、下载yolov5项目源码并运行3.5、pytorch的pt模型文件转onnx3.6、最…

vscode提升:JSON 中不允许有注释

解决方案 &#xff1a; 运行&#xff1a; json with comment 参考链接&#xff1a; https://blog.csdn.net/eqizhihui/article/details/134014010 人工智能学习网站 https://chat.xutongbao.top

音视频相关知识

H.264编码格式 音频 PCM就是要把声音从模拟信号转换成数字信号的一种技术&#xff0c;他的原理简单地说就是利用一个固定的频率对模拟信号进行采样。 pcm是无损音频音频文件格式 每秒15帧 一秒钟300kb 单位&#xff1a;像素

K8S的统一访问入口-Service

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:Linux运维老纪的首页…

金山云Q2调整后EBITDA率提升至3.2% 高质量发展驱动经营质效双增

8月20日&#xff0c;金山云公布了2024年第二季度业绩。 季度内&#xff0c;金山云整体业绩延续向好态势&#xff0c;实现收入规模、盈利能力、经营现金流的联动共赢。财报显示&#xff0c;金山云Q2营收18.9亿元&#xff0c;公有云实现收入12.3亿元&#xff0c;行业云实现收入6…