解密__牛客网

LinuX18

class Solution {
public:
    int numDecodings(string s) 
    {
         /** dp[i] 表示i的字符的合法编码数量，取决于当前字符
        dp[i] += dp[i-1],if s[i-1] ~('0'--'9')
        dp[i] += dp[i-2],if s[i-2] == '1' || (s[i-2]=='2' && s[i-1]>='0' && s[i-1]<='6')
        
    **/
        if(s.length()==0 || s[0] == '0')
            return 0;
        int len = s.length();
        vector<int> dp(len+1,0);
        dp[0]= 1,dp[1] = 1;
        for(int i=2;i<=len;i++)
        {
            if(s[i-1]>='1' && s[i-1]<='9')
                dp[i] += dp[i-1];
            if(s[i-2]=='1' || (s[i-2]=='2' && s[i-1]>='0' && s[i-1]<='6'))
                dp[i] += dp[i-2];            
        }
        return dp[len];                     
    }
};

发表于 2017-07-13 20:28:19 回复(4)

后劲好大

public class Solution {
    public int numDecodings(String s) {
        if(s == null || s.length() == 0 || s.charAt(0) == '0')
        	return 0;
        
        for(int i = 0; i < s.length(); i++){
        	if(!Character.isDigit(s.charAt(i)))
        		return 0;
        }
        
        // dp[i]表示s[0~i-1]可以有多少种解码方式
        // 递推方程：如果1 <= s[i-1] <= 9，则dp[i] += dp[i-1]；  
        // 如果10 <= s[i-2 ~ i-1] <= 26, 则dp[i] += dp[i-2].
        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) >= '1' && s.charAt(i-1) <= '9')
        		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()];
    }
}

发表于 2017-06-06 10:54:30 回复(0)

戴浩男

/*
 *	思路：dp题。
 *	状态定义：dp[i]表示s[0 ~ i-1]子串能解码的种类
 *	递推方程：如果1 <= s[i-1] <= 9，则dp[i] += dp[i-1]；  如果10 <= s[i-2 ~ i-1] <= 26, 则dp[i] += dp[i - 2].
 *	初始状态：dp[0] = 1, dp[1] = 1;
 *	注意：当s以0开头时，返回0
 */

public class Solution {
	public int numDecodings(String s) {
     	if (s.length() == 0 || s.startsWith("0"))
            return 0;
		int len = s.length() + 1;
        int[] dp = new int[len];
        dp[1] = 1;
        dp[0] = 1;
        for (int i = 2; i < len; i++) {
        	int t = Integer.valueOf(s.substring(i - 2, i));
        	if (10 <= t && t <= 26) {
        		dp[i] += dp[i - 2];
        	} 
        	//注意0在这里要特殊对待
        	int tmp = Integer.valueOf(s.substring(i - 1, i));
        	if (1 <= tmp && tmp <= 9) {
        		dp[i] += dp[i - 1];
        	}
        }
        return dp[len - 1];
    }
}

发表于 2016-08-15 23:16:15 回复(4)

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)

revivedSuN

import java.util.*;
public class Solution {
	public int numDecodings(String s) {
		if (s.length() == 0 || s.charAt(0) == '0') return 0; if (s.length() == 1) return 1; int f[] = new int[s.length() + 1];
		f[0] = 1; // 当有0个字符时候的编码个数，当有连续两个字符能编码时f[i] = f[i-2]，保证f[0]有值
		f[1] = 1; // 字符串长度为1时的编码个数
		for (int i = 1; i < s.length(); i++) {
			String num = s.substring(i - 1, i + 1);
            // 两个字符能否拼成一个编码
			if (Integer.valueOf(num) <= 26 && s.charAt(i - 1) != '0') {
				f[i + 1] = f[i + 1 - 2];
			} 
            // 单个字符能够构成编码，如果含0，则不能编码。
			f[i + 1] += s.charAt(i) != '0' ? f[i + 1 - 1] : 0;
		}
		return f[s.length()];
	}
}

编辑于 2016-10-16 15:49:32 回复(0)

实在学不动了

/*解题思路，
设dp[i+1]为s.sub(0,i)的解码个数
1.当s的第i个字符为0时，要想s.sub(0,i-1)加入这个‘0’后还能解码，就只能将s.sub(0,i-1)的最后一个字符尝试与'0'拼接，并且凭借后的字符还要小于26,否则，加上s.sub(0,i-1)加上'0'
后一定会导致s.sub(0,i)没有解码方式。所以综上所述只有s.at(i-1)=='1'或是s.at(i-1)=='2'才可以使拼接后小于26，并且此时s.sub(0,i)的解码个数和s.sub(0,i-2)一致。

2.当s的第i个字符为1~9时：
     （1）如果s.at(i-1)是'1'，那么，第i个字符可以单独解码，也可以与第i-1个字符合并组成一个码字，这种情况下s.sub(0,i)的解码个数为s.sub(0,i-1)的解码个数与s.sub(0,i-2)的解码个数之和。
      （2）如果s.at(i-1)是'2'且'6'>=s.at(i)>='1'，那么此时第i个符号也可以与i-1个合并，这种情况下s.sub(0,i)的解码个数同样为s.sub(0,i-1)的解码个数与s.sub(0,i-2)的解码个数之和。
      （3）其他情况下，也就是'7'<=s.at(i)<='9'&&s.at(i-1)=='2'和'1'<=s.at(i)<='9'&&3<=s.at(i-1)<=9这两种情况下，第i个字符不能与i-1个字符合并，只能自己单独作为一个码字，所以此时.sub(0,i)的解码个数和s.sub(0,i-1)一致。
*/
class Solution {
public:
    int numDecodings(string s) {
        if(s==""||s.at(0)=='0') return 0;
        int len_of_s=s.length();
        vector<int> dp(len_of_s+1);
        dp[0]=1;//空字符也是一种解码
        dp[1]=1;//如果s的第一个字符不是0，那么直到s的第一个字符含有1中解码
        for(int i=1;i<len_of_s;i++) {
            if(s.at(i)=='0') {
                if(s.at(i-1)=='1'||s.at(i-1)=='2') 
                    dp[i+1]=dp[i-1];
                else 
                    return 0;
            }
            else {
                if(s.at(i-1)=='1'||(s.at(i)<='6'&&s.at(i-1)=='2')) 
                    dp[i+1]=dp[i-1]+dp[i];
                else 
                    dp[i+1]=dp[i];
            }
        }
        return dp[len_of_s];
    }
};

/*方法2
class Solution { //***递归超时了
public:
    int numDecodings(string s) {

        int long_of_s=s.length(); 
        int decode_ways=0;
        int start;
        decode(decode_ways,0,long_of_s,s);
        return decode_ways;
    }
    void decode(int &decode_ways,int start,int long_of_s,string s) {
        for(int i=0;i<2;i++) { //i==0就是只包含start,i==1就是包含两位，最多只可能包含两位三位一定大于26
            if(start==long_of_s-1&&i==1) return;  //当到了s的最后一位，i就只能等于0，等于1就是错误的，所以在这个特例下需要return
            if((i==1&&stoi(s.substr(start,i+1))>9&&stoi(s.substr(start,i+1))<27)||(i==0&&stoi(s.substr(start,i+1))>0&&stoi(s.substr(start,i+1))<10)) {  //当从start开始截取i+1个符号对应的的数字小于26，之所以不采用stoi(s.substr(start,i+1))>0&&stoi(s.substr(start,i+1))<27)这种写法的原因是，防止在截取两位数时出现01、02...0x这种误判，这种情况是没有解码方式的，可以采样那种写法却会判定他们为一种解码方式
                if(start+i==long_of_s-1) {   //当发现这次截取已经包含s的最后一个字符，就停止向更深处递归，并方式加一
                    decode_ways++;
                    return;
                } 
                decode(decode_ways,start+i+1,long_of_s,s);  //没到最深处继续递归，如果i==0，那其实就是start下一位，i==1，就是下下一位
            }  
        }//其他的可能性就是从当从start开始截取i+1个还没到最后一位且对应的数字不在1~26范围内，此时我们不向更深处递归，等到i==2的时候如果还不满足截取数字在1~26的话，本次调用就自动结束了，不用做多于处理！
    }
};*/

发表于 2020-06-23 12:53:33 回复(0)

张佃鹏

public class Solution {
    public int numDecodings(String s) {
        int size = s.length();
        if(size == 0) return 0;
        int[] dp = new int[size + 2];
        dp[0] = 1; dp[1] = 1;
        for(int i = 2; i <= size + 1; i++){
            dp[i] = dp[i - 2] * isOk(s, i - 3, i - 1) + dp[i - 1] * isOk(s, i - 2, i - 1);
        }
        return dp[size + 1];
    }
    public int isOk(String s, int begin, int end){
        if(begin < 0) return 0;
        String subStr = s.substring(begin, end);
        int value = Integer.parseInt(subStr);
        return value <= 26 && value >= 1 && Integer.toString(value).length() == subStr.length() ? 1 : 0;
    }
}

发表于 2019-11-06 12:15:37 回复(0)

萧萧木叶201904271117960

class Solution {
public:
    int numDecodings(string s) {
        int len = s.length();
        if(len==0||s[0]=='0') return 0;
        int dp[100000];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=len;i++){
            if((s[i-2]=='2'&&s[i-1]<='6') || (s[i-2]=='1'&&s[i-1]<='9')){
                //状态转移方程
                dp[i]=dp[i-1]+dp[i-2];
                if(s[i-1]=='0') dp[i]=dp[i-2];
            }else if(s[i-1]=='0'){
                return 0;
            }else{
                dp[i]=dp[i-1];
            }
        }
        return dp[len];
    }
};

发表于 2019-07-04 23:21:20 回复(0)

生田小花花

什么时候我能自己写出来就好了，这个是参考大佬们的结果写的

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

发表于 2019-01-29 15:06:39 回复(2)

C/C++

J.Fan

class Solution {
public:
    bool isValid(string s)
    {
        stringstream ss(s);
        int num;
        ss >> num;
        if(s.size()>1)
            return s[0]!='0' && num>=1 && num<=26;
        return num>=1 && num<=26;
    }
    int numDecodings(string s) {
        int len=s.size();
        if(len ==0 )
            return 0;
        vector<int> dp(len+1);
        dp[0] = 1;
        string s1;
        for(int i=1;i<=len;i++)
        {
            for(int j=0;j<i;j++)
            {
                s1 = s.substr(j,i-j);
                if(isValid(s1))
                {
                    dp[i] += dp[j];
                }
            }
        }
        return dp[len];
    }
};

发表于 2019-01-02 18:32:56 回复(0)

C/C++

NJ

这道题思考了两天半才完全弄明白。。。
class Solution
{
public:
    int numDecodings(string s)
    {
        int len=s.size();
        if(len<=0)
            return 0;
        vector<int> dp(len+1);
        dp[0]=1;
        if(s[0]!='0')
            dp[1]=1;
        else
            dp[1]=0;
        for(int i=2;i<=len;++i)
        {
            if(s[i-1]!='0')
                dp[i]=dp[i-1];
            else
                dp[i]=0;
            if(s[i-2]=='1'||(s[i-2]=='2'&&s[i-1]<='6'))
                dp[i]=dp[i]+dp[i-2];
        }
        return dp[len];
    }
};

发表于 2017-11-28 19:35:29 回复(0)

C/C++

nbgao

class Solution {
public:
    int numDecodings(string s) {
        int l = s.length();
        if(l==0 || s[0]=='0')
            return 0;
        vector<int> dp(l+1,0);
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2;i<=l;i++)
        {
            if(s[i-1]>='1' && s[i-1]<='9')
                dp[i] += dp[i-1];
            if(s[i-2]=='1' || (s[i-2]=='2' && s[i-1]>='0' && s[i-1]<='6'))
                dp[i] += dp[i-2];         }
        return dp[l];     }
};

发表于 2017-10-06 01:24:59 回复(0)

王大爷

class Solution {
public:
    int numDecodings(string s) {
        if(s.empty())return 0;
        vector<int> dp(s.size(),0);
        dp[0]=s[0]-'0'>0?1:0;
        for(int i=1;i<s.size();++i){
            int tmp=stoi(s.substr(i-1,2));
            dp[i]=(s[i]-'0'>0?dp[i-1]:0)+(tmp<=26 && tmp>=10?(i==1?1:dp[i-2]):0);
        }
        return dp[s.size()-1];
    }
};

发表于 2017-09-07 14:56:01 回复(0)

JacobGo！

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

		return res[0];
	}

发表于 2017-07-10 12:53:24 回复(0)

ptj

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

发表于 2017-07-04 23:51:22 回复(0)

whisky_

int numDecodings(string s) {

if(s.empty()||s.front()=='0')

return 0;

vector<int> ways{1, s.back()!='0'};

for(int i=s.size()-2; i>=0; --i)

if(s[i]=='0')

ways.push_back(0);

else{

int val=(s[i]-'0')*10+s[i+1]-'0';

if(val==0)

return 0;

if(val>26)

ways.push_back(ways.back());

else

ways.push_back(ways.back()+*(ways.end()-2));

}

return ways.back();

发表于 2017-05-12 18:58:30 回复(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)

C/C++

华科不平凡

这个动态规划有点难，因为f(i)不仅与f(i-1)有关，和f(i-2)也有关系，能想明白这一层关系着实不容易0.0

设当前的解法有f(i)种，由于s[i]和s[i - 1]的搭配方式有多种，下面分情况讨论：

非法的情况，即不论怎么搭配都decode不了，返回0
合法的情况，如果只能搭配成一种，那么f(i)=f(i-1)，如果能搭配成两种，那么f(i)=f(i-1)+f(i-2)

class Solution {
public:
    /**
     *
     * @param s string字符串
     * @return int整型
     */
    int numDecodings(string s) {
        // write code here
        if(s.size() < 1 || s[0] == '0') return 0;
        int a = 1, b = 1, dp = 1;
        for (int i = 1; i < s.size(); ++i) {
            // 非法的情况
            if (s[i] == '0' && (s[i - 1] > '2' || s[i - 1] == '0')) return 0;
            // 合法的情况之可拆
            if (s[i] != '0' && ((s[i - 1] == '1') || (s[i - 1] == '2' && s[i] < '7'))) dp = a + b;
            // 合法的情况之不可拆
            else dp = b;
            a = b; b = dp;
        }
        return dp;
    }
};

发表于 2020-08-11 11:12:11 回复(0)

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)

BSXRB

    public int numDecodings (String s) {
        // write code here
        char cs[] = s.toCharArray();
        int n = cs.length;
        int[] dp = new int[n];
        if (n==0) return 0;
        if ("0".equals(s)) return 0;
        if (n==1) return 1;
        if (cs[1]!='0'&&((cs[0]=='1')||(cs[0]=='2'&&cs[1]<='6'))){
            dp[0] = 1;
            dp[1] = 2;
        }else {
            dp[0] = 1;
            dp[1] = 1;
        }
        for (int i = 2; i < n; i++) {
            if (cs[i]=='0'&&(cs[i-1]=='1'||cs[i-1]=='2')) dp[i] = dp[i-2];
            else if (cs[i]==0) return 0;
            else if (cs[i-1]=='0') dp[i] = dp[i-1];
            else if (cs[i-1]=='1') dp[i] = dp[i-1] + dp[i-2];
            else if (cs[i-1]=='2'&&cs[i]<='6') dp[i] = dp[i-1] + dp[i-2];
            else dp[i] = dp[i-1];
        }
        return dp[n-1];
    }

发表于 2020-07-31 16:37:50 回复(0)

解密

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题