解码
程序员文章站
2022-07-05 16:11:18
...
一条包含字母 A-Z 的消息通过以下映射进行了 编码 :
'A' -> 1
'B' -> 2
...
'Z' -> 26
要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,"11106" 可以映射为:
"AAJF" ,将消息分组为 (1 1 10 6)
"KJF" ,将消息分组为 (11 10 6)
注意,消息不能分组为 (1 11 06) ,因为 "06" 不能映射为 "F" ,这是由于 "6" 和 "06" 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/decode-ways
思路:从第一个字符到当前字符这一部分的解码方法数为f(i),对于第i个字符,若当前字符能解码,f(i) = f(i - 1),
若当前字符加上上一个字符能解码f(i) = f(i - 2),最终f(i) = f(i - 1) + f(i - 2)。
public int numDecodings(String s) {
if (s.charAt(0) == '0'){
return 0;
}
int f1 = 1;
int f2 = 1;
for (int i = 1; i < s.length(); i++){
int f = 0;
if (s.charAt(i) <= '9' && s.charAt(i) >= '1') {
f += f2;
}
if (s.substring(i - 1,i + 1).compareTo("26") <= 0 && s.substring(i - 1,i + 1).compareTo("10") >= 0){
f += f1;
}
if (f == 0){
return 0;
}
f1 = f2;
f2 = f;
}
return f2;
}
上一篇: mediacodec编码camera视频
下一篇: node.js基础知识小结