推文最好的网站是哪个,wordpress制作网站步骤,吉安网站设计,郑州网站seo技术来源#xff1a;LeetCode第91题
难度#xff1a;中等
描述#xff1a;一条包含字母A-Z的消息通过以下映射进行了编码: A-1,B-2,z-26,要接吗已编码的消息#xff0c;所有数字必须基于上述映射的方法#xff0c;反向映射回字母(可能由多种方法)#xff0c;例…来源LeetCode第91题
难度中等
描述一条包含字母A-Z的消息通过以下映射进行了编码: A-1,B-2,z-26,要接吗已编码的消息所有数字必须基于上述映射的方法反向映射回字母(可能由多种方法)例如11106可以映射成AAJF,将消息分组为(1 1 10 6),注意消息不能分组为(1 11 06)因为06不能映射成F这是因为6和06在映射中并不等价。 示例1 输入s12; 输出2 解释他可以解码为AB(1 2)或者L(12);
第一种求解方法递归
//定义一个递归函数String s表述输入的字符串index表示开始进行判断的索引
public int numDecode(String s,int index)
{
//当索引大于s.length()的时候表明已经找到了一个路径返回1这是作为递归的终止条件if(indexs.length())
return 1;int res0;
if(s.charAt(index)!0)
{
//这个判断标准表明s.chaeAt(index)可以作为单独的一个字母从而可继续向下走
resnumDecode(s,index1);
}
//以1开头或以2开头且第二个字母小于6(26)两者均要满足下一个字母存在
if(((index1)s.length()-1)(s.charAt(index)1||(s.charAt(index)2s.charAt(index1)6)))
{
resnumDecode(s,index2);
}
map[index]res;
return res;
}
在进行递归操作的时候很多情况下会出现重复计算从而可以使用一个map实现计算过得值的一个存储从而使得不用进行重复计算
public int numDecode(String s,int index,int []map)
{
if(indexs.length())
return 1;
int res0;
if(map[index]!-1)
{
return resmap[index];
}
if(s.charAt(index)!0)
{
resnumDecode(s,index1,map);
}
if((index1s.length()-1)((s.charAt(index)1)||(s.charAt(index)2||(s.charAt(index1)6))))
{
resnumDecode(s,Index2,map);
}
}
public void NumDecode(String s)
{
int []mapnew int [s.length()];
numDecode(s,0,map);
}
动态规划求解除此之外还可以使用动态规划进行求解每一次可以走一步也可以走两步 public int numDecode3(String s,int index)
{
int dp[]new int[s.length()];
if(s.charAt(0)0)
{
dp[0]0
}else
{
dp[0]1;
}
for(int i1;is.length();i)
{
if(s.charAt(i)!0)
{
dp[i]dp[i-1]
}else
{
dp[i]0;
}
if(i2)
{
if((i1s.length()-1)((s.charAt(i)1)||(s.charAt(i)2s.charAt(i1)6)))
{
dp[i]dp[i-2];
}
}
}
return dp[s.length()-1]
}
