首页 > 试题广场 >

解密

[编程题]解密

热度指数：21944 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

一条仅包含字母‘A’-‘Z’的消息用下列的方式加密成数字

'A' -> 1
'B' -> 2
...
'Z' -> 26

现在给出加密成数字的密文，请判断有多少种解密的方法

例如：

给出的密文为“13”，可以解密为"AC"(1 3) 或者"M"(13).

所以密文"13"的解密方法是2种.

示例1

输入

"1"

输出

示例2

输入

"13"

输出

算法知识视频讲解

Java

日常不想上班的码农

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int numDecodings (String s) {
        char[] charArray = s.toCharArray();
		int length = charArray.length;
		if (length <= 0 ||charArray[0] == '0') {
			return 0;
		}
		int[] dp = new int[length];
		dp[0] = 1;
		for (int i = 1; i < length; i++) {
			if (charArray[i] != '0') {
				dp[i] = dp[i - 1];
			}
			int num = 10 * (charArray[i - 1] - '0') + (charArray[i] - '0');
			if (num >= 10 && num <= 26){
				if (i == 1) {
					dp[i] ++;
				}
				else {
					dp[i] += dp[i - 2];
				}
			}
		}
		return dp[length - 1];
    }
}

发表于 2020-08-02 23:40:36 回复(0)

Java

干不死往死里干

public class Solution {
    public int numDecodings(String s) {
        if(s.length()==0||s.charAt(0)=='0'){
            return 0;
        }
        int dp[] = new int[s.length() +1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=s.length();i++){
            if(s.charAt(i-1)!='0'){
                dp[i] += dp[i-1];
            }
            if(Integer.valueOf(s.substring(i-2,i))>=10
               && Integer.valueOf(s.substring(i-2,i))<=26){
                dp[i] +=dp[i-2];
            }
        }
        return dp[s.length()];
    }
}

发表于 2019-08-20 23:44:50 回复(0)

Java

Yuerya

dp[2][s.length()]

第一行dp[0]保存最后一个分割为一位数的个数

第二行dp[1]保存最后一个分割为两位数的个数

每列上下两个加起来即为总个数

判断下一位时：

1. 下一位为0，不存在最后一位分割（0不对应任何字母）

否则，dp[0][i] = dp[0][i-1] + dp[1][i-1]，将i数字作为单独新分割加到前一位的所有分割后面

2. 如果前一位和当前位组合小于等于26，dp[1][i] = dp[0][i-1]，将数字延续到前一位的单独分割后面

否则为0

s	1	12	120	1207	12072	120723
dp[0]	1	1	0	1	1	1
dp[1]	0	1	1	0	0	1

public class Solution {
    public int numDecodings(String s) {
        if(s.length() == 0 || s.charAt(0) == '0'){
            return 0;
        }
        int[][] dp = new int[2][s.length()];
        dp[0][0] = 1;
        dp[1][0] = 0;
        for(int i = 1; i < s.length();i++){
            if((int)s.charAt(i) == '0'){
                dp[0][i] = 0;
            }else{
                dp[0][i] = dp[0][i-1] + dp[1][i-1];
            }
            
            if((s.charAt(i-1)-'1'+1)*10+(s.charAt(i)-'1'+1) <=26){
                dp[1][i] = dp[0][i-1];
            }else{
                dp[1][i] = 0;
            }
        }
        return dp[0][s.length()-1]+dp[1][s.length()-1];
    }
}

发表于 2019-04-12 00:21:59 回复(0)

Java

齐鱼鱼

    public static int numDecodings(String s) {
        int n=s.length();
        int[] dp=new int[n+1];
        dp[n]=1;
        dp[n-1]=(s.charAt(n-1)=='0')?0:1;
        for(int i=n-2;i>=0;i--){
            if(s.charAt(i)=='0')continue;
            if(Integer.valueOf(s.substring(i,i+2))<=26){
                dp[i]=dp[i+1]+dp[i+2];
            }else{
                dp[i]=dp[i+1];
            }
        }
        return dp[0];
    }

zhuyi'0'

发表于 2018-09-06 11:38:15 回复(0)

Java

回到过去201808221133636

//主要分四种情况讨论

public class Solution {

public int numDecodings(String s) {
if(s==null||s.length()==0)
return 0;
char[] ws = s.toCharArray();
int c1 = 0;
int c2 = 0;
int count=0;
if(ws[0]<='9'&&ws[0]>='1'){
c2=1;
c1=1;
count=1;
}
for(int i=1; i<ws.length; ++i) {
char a = ws[i-1];

char b = ws[i];

//当前字符独立解码或者与上一字符合并解码

if((a=='1'&&b>='1'&&b<='9') || (a=='2'&&b>='1'&&b<='6')) {
count = c1+c2;
} else if((a=='1'&&b=='0') || (a=='2'&&b=='0')) { //当前字符只能与上一字符合并解码
count = c1;
} else if (b>='1'&&b<='9') {//当前字符只能独立解码
count = c2;
} else {//当前字符不合法
return 0;
}

    c1=c2;

c2=count;
}
return count;
}
}

发表于 2018-08-22 15:58:23 回复(0)

Java

pp11

public class Solution {
    public int numDecodings(String s) {
    	if (s == null || s.length() == 0)
    		return 0;
    	int n = s.length();
    	int[] dp = new int[n + 1];
    	dp[0] = 1;
    	dp[1] = s.charAt(0) == '0' ? 0 : 1;
    	for (int i = 2; i <= s.length(); ++i) {
    		int oneBit = Integer.parseInt(s.substring(i - 1, i));
    		int twoBit = Integer.parseInt(s.substring(i - 2, i));
    		if (oneBit >= 1 && oneBit <= 9) {
    			dp[i] += dp[i - 1];
    		}
    		if (twoBit >= 10 && twoBit <= 26) {
    			dp[i] += dp[i - 2];
    		}
    	}
        return dp[n];
    }
}

发表于 2017-08-11 13:57:05 回复(0)

Java

Zfirsty

public class Solution {
    public int numDecodings(String s) {
        if(s.length()==0) return 0;
        int [] dp = new int[s.length()+1];
        dp[0]=1;
        if(s.length()>0&&s.charAt(0)>'0')
        dp[1]=1;
        for(int i=2;i<=s.length();i++){
            if(s.charAt(i-1)>'0')
              dp[i]=dp[i-1];
            if(s.charAt(i-2)>'0'){
            int t  =Integer.parseInt(s.substring(i-2,i));
            if(t<=26&&t>0) 
              dp[i]+=dp[i-2];
        	}
        }
        return dp[s.length()];
    }
}

发表于 2017-08-02 10:31:33 回复(0)

Java

恶变133

public static int numDecodings(String s) {

if(s==null || s.equals(""))
{
return 0;
}
int len = s.length();
int [] count = new int [len+1];
//数组0元素的值和1元素的值需要动态赋值：当第一位为0时，表示该信息无法译码
count[0] = (Integer.parseInt(""+s.charAt(0))>=1 && (Integer.parseInt(""+s.charAt(0))<=9)?1:0);
count[1] = (Integer.parseInt(""+s.charAt(0))>=1 && (Integer.parseInt(""+s.charAt(0))<=9)?1:0);
for(int i = 2;i<=len;i++)
{
//有固定最后一位和固定最后两位的情况。
String str1 = new String(""+s.charAt(i-1));
String str2 = new String(""+s.charAt(i-2)+s.charAt(i-1));
int value1 = Integer.parseInt(str1);
int value2 = Integer.parseInt(str2);
count[i] = ((value1>=1 && value1<=9)?count[i-1]:0) + ((value2>=10 && value2<=26)?count[i-2]:0);
}
return count[len];
}

编辑于 2017-06-26 21:11:49 回复(0)

Java

Holiday_12138

public class Solution {
    public int numDecodings(String s) {
        if(s.length() < 1 || s.charAt(0) == '0')
            return 0;
        
        int[] dp = new int[s.length()+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2; i<=s.length(); i++) {
            if(s.charAt(i-1) != '0')
            	dp[i] += dp[i-1];
            if(s.charAt(i-2) == '1' || (s.charAt(i-2) == '2' && s.charAt(i-1) <= '6' && s.charAt(i-1) >= '0'))
                dp[i] += dp[i-2];
        }
        return dp[s.length()];
    }
}

发表于 2017-06-25 13:53:20 回复(0)

Java

城市里的养猫者

public class Solution { public int numDecodings(String s) { int n = s.length(); if (n == 0) return 0; int[] memo = new int[n+1];
        memo[n]  = 1;
        memo[n-1] = s.charAt(n-1) != '0' ? 1 : 0; for (int i = n - 2; i >= 0; i--) if (s.charAt(i) == '0') continue; else memo[i] = (Integer.parseInt(s.substring(i,i+2))<=26) ? memo[i+1]+memo[i+2] : memo[i+1]; return memo[0];
    }
}