当前位置:网站首页>【JZ46 把数字翻译成字符串】
【JZ46 把数字翻译成字符串】
2022-04-23 14:33:00 【Sugar_wolf】
描述
有一种将字母编码成数字的方式:'a'->1, 'b->2', ... , 'z->26'
。
我们把一个字符串编码成一串数字,再考虑逆向编译成字符串。
由于没有分隔符,数字编码成字母可能有多种编译结果,例如 11
既可以看做是两个 'a'
也可以看做是一个 'k'
。但 10
只可能是 'j'
,因为 0
不能编译成任何结果。
现在给一串数字,返回有多少种可能的译码结果
数据范围:字符串长度满足 0 < n ≤ 90
进阶:空间复杂度 O(n),时间复杂度 O(n)
示例1
输入: "12"
返回值:2
说明:2种可能的译码结果(”ab” 或”l”)
示例2
输入: "31717126241541717"
返回值:192
说明:192种可能的译码结果
分析:
-
首先对数据进行分类,对于空字符串、首字符为
‘0’
的字符串,以及‘0’
的前一位不是‘1’
或者‘2’
的字符串,输出0
; -
建立一个动态数组
dp[len+1]
,用于存储有几种译码结果。dp[0]=1,dp[1]=1。
1)若第k个字符和第
k-1
个字符能够组合成a到z的合法字符,则dp[k+1]=dp[k]+dp[k-1];
2)若无法组成合法字符,则译码结果没有增加,
dp[k+1]=dp[k];
3)若第k个字符和第
k-1
个字符中有‘0’
,则无法产生新的译码方式,dp[k+1]=dp[k]
;
代码:
class Solution {
public:
int solve(string nums) {
int len = nums.size();
if (len == 0)
return 0;
for (int k = 0;k < len;k++)
{
if (nums[k]=='0')
{
if (k == 0)
return 0;
else if (nums[k-1] != '1' && nums[k-1] != '2')
return 0;
}
}//如果0位于第一位或者0的前面不是1或者2,则无法进行译码
int dp[len+1],temp;
dp[0] = 1;
dp[1] = 1;
for (int k=1;k<len;k++)
{
temp=(nums[k]-'0')+(nums[k-1]-'0')*10;
if (temp > 0 && temp <= 26 && nums[k]!= '0'&& nums[k-1] != '0')
dp[k+1] = dp[k]+dp[k-1];
else
dp[k+1] = dp[k];
}
return dp[len];
}
};
运行时间:6ms
超过15.56% 用C++提交的代码
占用内存:424KB
超过46.36%用C++提交的代码
版权声明
本文为[Sugar_wolf]所创,转载请带上原文链接,感谢
https://blog.csdn.net/Sugar_wolf/article/details/124333220
边栏推荐
猜你喜欢
Tongxin UOS uninstall php7 2.24, install php7 4.27 ; Uninstall and then install PHP 7.2.34
C语言知识点精细详解——初识C语言【1】
Proteus simulation design of DC adjustable regulated power supply (with simulation + paper and other data)
TLS/SSL 协议详解 (30) SSL中的RSA、DHE、ECDHE、ECDH流程与区别
Design of single chip microcomputer Proteus for temperature and humidity monitoring and alarm system of SHT11 sensor (with simulation + paper + program, etc.)
555 timer + 74 series chip to build eight way responder, 30s countdown, proteus simulation, etc
8.5 循环神经网络简洁实现
1N5408-ASEMI整流二极管1N5408
【NLP】HMM隐马尔可夫+维特比分词
Multisim Simulation Design of DC adjustable regulated power supply of LM317 (with simulation + paper + reference)
随机推荐
Parameter stack pressing problem of C language in structure parameter transmission
ASEMI超快恢复二极管与肖特基二极管可以互换吗
source insight via samba
拼接hql时,新增字段没有出现在构造方法中
Some little records~
电子秤称重系统设计,HX711压力传感器,51单片机(Proteus仿真、C程序、原理图、论文等全套资料)
外包幹了四年,廢了...
C语言知识点精细详解——初识C语言【1】——你不能不知的VS2022调试技巧及代码实操【2】
四层和八层电梯控制系统Proteus仿真设计,51单片机,附仿真和Keil C代码
一款不错的工具:aardio
JS parabola motion packaging method
asp.net使用MailMessage发送邮件的方法
A blog allows you to learn how to write markdown on vscode
8.3 语言模型与数据集
XX project structure notes
Redis源码分析之PSYNC同步
API Gateway/API 网关(四) - Kong的使用 - 集成Jwt和熔断插件
Proteus simulation design of four storey and eight storey elevator control system, 51 single chip microcomputer, with simulation and keil c code
【Proteus仿真】自动量程(范围<10V)切换数字电压表
Matlab Simulink modeling and design of single-phase AC-AC frequency converter, with MATLAB simulation, PPT and papers