有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。
现在给一串数字，给出有多少种可能的译码结果。
[编程题]解码
//商汤笔试题是真的难，限时做的话，只有大佬才做得完吧。
//解题思路：动态规划 定义dp[i]表示以第i个字母结束可能的编码数(i取值0到len-1) , dp[i]全部初始化为0
//动态方程如下：
// dp[i]+=dp[i-1] ，如果第i位！='0'
// dp[i]+=dp[i-2], 如果第i-1位和第i位可以组成一个合法表示也就是10到26之间
//接下来就是考虑初值dp[0]和dp[1]
// dp[0]=1，如果第0位！='0'
// dp[0]=0，其他情况
// dp[1]=2，如果第0位和第1位组成的数在11到19或21到26
// dp[1]=0, 如果第0位和第1位组成的数是00，01...09或者30，40...90
// dp[1]=1, 其他
//计算dp[1]时，情况比较多，最后可以计算并集，三种情况并集是00到99，看是否漏掉。
//另外，如果dp[0]或者dp[1]==0,直接输出0结束程序
#include<iostream>
#include<vector>using namespace std;
int main() {
string s;
cin>>s;
int len=s.size();
vector<int> dp(len,0);
if(len==0) {
cout<<0;
return 0;
}
for(int i=0;i<len;i++) {
if(i==0) { //dp[0]赋初值
if(s[0]!='0')
dp[0]=1;
else{
dp[0]=0;
cout<<0;
return 0;
}
}
else if(i==1) { //dp[1]赋初值
if( (s[0]=='1'&&s[1]>='1'&&s[1]<='9') || (s[0]=='2'&&s[1]>='1'&&s[1]<='6'))
dp[1]=2;
else if(s[0]=='0' || (s[0]>='3'&&s[1]=='0')) {
dp[1]=0;
cout<<0;
return 0;
}
else
dp[1]=1;
}else { //计算其他dp[i]
if(s[i]!='0')
dp[i]+=dp[i-1];
if(s[i-1]=='1' || (s[i-1]=='2'&&s[i]<='6'))
dp[i]+=dp[i-2];
/*
if(dp[i]==0) {
cout<<0;
return 0;
}
*/
}
}
cout<<dp[len-1];
return 0;
}
编辑于 2020-08-19 10:52:13
回复(0)
def fibonacci(n): ##计算连续n个两两都小于27的数字可以有多少种编码方式，比如 1212 一共有5种
if n < 3:
return n
return fibonacci(n-1) + fibonacci(n-2)
def sol(a):
if a == "0":
return 0
if "00" in a:
return 0 ## 连续两个0，则一定无法编码
str_1 = "" ## 保存那些位上的数字可以和之后的组成小于27的数字
for i in range(len(a)-1):
if int(a[i:i+2])<=26 and int(a[i])>0 and int(a[i+1])!=0:
str_1 += "1"
else:
str_1 += "0"
s = 1
l1 = str_1.strip().split("0")
for x in l1:
s *= fibonacci(len(x)+1)
return s
print(sol(a))
发表于 2019-08-19 16:25:16
回复(0)
import java.util.Scanner;
public class Main {
public static int process(char[] ch, int i) {
if (i == ch.length) {
return 1;
}
if (ch[i] == '0') {
return 0;
}
if (ch[i] == '1') {
int res = process(ch, i + 1);
if (i + 1 < ch.length) {
res += process(ch, i + 2);
}
return res;
}
if (ch[i] == '2') {
int res = process(ch, i + 1);
if (i + 1 < ch.length && ch[i] >= '0' && ch[i + 1] <= '6') {
res += process(ch, i + 2);
}
return res;
}
return process(ch, i + 1);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
if (str.length() < 1) {
System.out.println(0);
} else {
System.out.println(process(str.toCharArray(), 0));
}
}
}
发表于 2019-06-12 22:44:19
回复(0)
动态规划。
这里做题为了节约时间先不考虑节约内存的建立备忘录方法，直接递归。
边际为f(一位数) = 1, f(两位数) = 2或1（当超过26时为1）
f(str) = f(str切掉最后一位) + f(str切掉最后两位) ，str切掉最后两位小于26
或
f(str) = f(str切掉最后一位) ，str切掉最后两位大于26
function f(str) {str = str.toString() // 参数转成字符串let arr = str.split('')if (arr.length === 1) // 参数只有一位，那么返回的种类就一种return 1}if (arr.length === 2) { // 参数字符串两位位，那种类就取决于这个两位数的大小if (parseInt(arr[0] + arr[1]) <= 26) {return 2 // 小于等于26就能转化为一个字母，那么就有两种字母对应方式} else {return 1 // 大于26就能转化为一个字母，那么只有一种字母对应方式}}let arr1 = arr.concat() // 防止数组的引用传递，这里拷贝一份arr1.pop() // 去掉后一位let str1 = arr1.join('')let arr2 = arr.concat()if (parseInt(arr2.slice(-2).join('')) > 26) { // 判断被去掉的两位数是否大于26return f(str1) // 递归，种类数仅有f(str切掉后一位)} else {arr2.pop()arr2.pop()let str2 = arr2.join('')return f(str1) + f(str2)// 递归，种类数有f(str切掉后一位) + f(str切掉后2位)种}}
编辑于 2018-09-03 20:22:42
回复(1)
string =input()
length =len(string)
if(string[0] ==str(0)):
print(0)
else:
pre =[1, 0]
end =[0, 0]
fori inrange(1,length):
if(string[i] ==str(0)):
end[0] =0
else:
end[0] =pre[0] +pre[1]
if(string[i-1] ==str(0)) or(int(string[i-1]) > 2) or(string[i-1] ==str(2) andint(string[i]) > 6):
end[1] =0
else:
end[1] =pre[0]
pre =end.copy()
print(pre[0]+pre[1])
发表于 2018-08-17 14:57:27
回复(0)
# -*- coding:utf-8 -*- #python解法''' dp(n):n个字符可能的结果 1.s[i-2]和s[i-1] 两个字符是10----26之间但不包括10和20这两个数时： eg:判断“567123”的编码方式可以转为判断“56712”+‘3“或者”5671“+”23“的问题。即dp(n)=dp(n-1)+dp(n-2)。 2.s[i-2]和s[i-1] 两个字符10或20这两个数时，只有一种编码方式，比如10------>[“J”], 所以dp[i] = dp[i-2] 3.s[i-2]和s[i-1] 两个字符不在上述两种范围时，比如27，所以dp[i] = dp[i-1] 4.数字”0“对应的编码只能是和其前一个数字组合对应的编码，如果和其前一个字符组合后不存在对应编码，则编码方式为0. ''' dp = [1,1] s = raw_input().strip() if s=='' or s[0]=='0': dp = [0,0] #此时下面的for不会运行，也不报错 for i in range(2, len(s) + 1): if 10 <= int(s[i - 2:i]) <= 26 and s[i - 1] != '0': # 1 dp.append(dp[i - 1] + dp[i - 2]) elif int(s[i - 2:i]) == 10 or int(s[i - 2:i]) == 20: # 2 dp.append(dp[i - 2]) elif s[i - 1] != '0': # 3 dp.append(dp[i - 1]) else: dp.append(0) # 4 print dp[len(s)]
编辑于 2019-03-04 01:57:29
回复(2)
#include<bits/stdc++.h>
using namespace std;
int numDecodings(string s) {
if(!s.size() || s.front() == '0') return 0;
int r1 = 1, r2 = 1;
for (int i = 1; i < s.size(); i++){
if (s[i] == '0') r1 = 0;
if (s[i-1] == '1' || s[i-1] == '2' && s[i] <= '6'){
r1 = r2+r1;
r2 = r1-r2;
}
else
r2 = r1;
}
return r1;
}
int main(){
string s;
while(cin >> s){
cout << numDecodings(s) << endl;
}
return 0;
}
LeetCode #91。
发表于 2018-08-22 21:11:37
回复(7)
C++ 动态规划方法
主要有四种情况
- 当前字符与前一位可以组成10或20
- 当前字符与前一位可以组成11到26之间（不含20）
- 当前字符和前一位可以组成30,40,...,90
- 其它
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int numOfDecodings(string s) {
int len = s.size();
if (!len || s[0] == '0') return 0;
vector<int> nums(len, 0);
nums[0] = 1;
if (s[1] == '0' && s[0] <= '2') nums[1] = 1;
else if (s[0] == '1' || (s[0] == '2' && s[1] <= '6')) nums[1] = 2;
else if (s[1] == 0) nums[1] = 0;
else nums[1] = 1;
for (int i = 2; i < len; ++i) {
if (s[i] == '0' && s[i - 1] <= '2' && s[i - 1] > '0') nums[i] = nums[i - 2];
else if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6')) nums[i] = nums[i - 1] + nums[i - 2];
else if (s[i] == '0') nums[i] = 0;
else nums[i] = nums[i - 1];
}
return nums[len - 1];
}
int main(void) {
string in;
int num = 0, len = in.length();
cin >> in;
cout << numOfDecodings(in) << endl;
return 0;
}
发表于 2018-09-04 17:16:39
回复(1)
if __name__ == "__main__": s = str(input()) if s == '' or s[0] == '0': print(0) exit() dp = [1] for i in range(1, len(s) + 1): dp.append((0 if (s[i - 1] == '0') else dp[i - 1])) if(i > 1 and (s[i - 2] == '1' or (s[i - 2] == '2' and s[i - 1] <= '6'))): dp[i] += dp[i - 2] print(dp[len(s)])
发表于 2019-08-21 09:27:14
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.nextLine();
back(s, 0);
System.out.println(cnt);
}
// 数字转字母的编码需要考虑0-回溯爆搜
static int cnt = 0;
public static void back(String s, int idx) {
if (idx == s.length()) {
cnt++;
return;
}
// 选一个
int i = s.charAt(idx) - '0';
if (i > 0 && i <= 9) {
back(s, idx + 1);
}
// 选两个
if (idx+1 <= s.length()-1) {
int j = s.charAt(idx+1) - '0';
int sum = i * 10 + j;
if (sum >= 10 && sum <= 26) {
back(s, idx + 2);
}
}
}
}
发表于 2022-07-10 13:18:39
回复(0)
#include <bits/stdc++.h>
using namespace std;
int numDecodings(string s) {
if (s[0] == '0') return 0;
vector<int> dp(s.size() + 1, 0); // dp[i]表示前i个字符可能的解码结果
dp[0] = 1; dp[1] = 1;
for (int i = 2; i <= s.size(); i++) {
if (s[i - 1] == '0') { // 字符下标从0开始，这里i从2开始，所以用i - 1索引当前字符下标
if (s[i - 2] == '1' || s[i - 2] == '2') { // 单独考虑10和20
dp[i] = dp[i - 2];
}else {
return 0;
}
}else {
int num = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
if (num >= 10 && num <= 26) { // 因为当前字符不可能为0，所以在10和26之间的数不可能是10和20
dp[i] = dp[i - 1] + dp[i - 2];
}else {
dp[i] = dp[i - 1];
}
}
}
return dp[s.size()];
}
int main() {
string s;
cin >> s;
int result = numDecodings(s);
cout << result << endl;
return 0;
}
发表于 2021-11-21 10:22:08
回复(0)
动态规划，注意细节
#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{
string str;
cin >> str;
int n = str.length();
int bZero = false;
if (str[0]=='0') bZero = true;
for (int i = 1; i < n; ++i)
{
if (str[i]=='0'&&str[i-1]=='0')
{
bZero = true;
break;
}
}
if (bZero)
{
printf("0\n");
return 0;
}
vector<int> dp(n+1, 0);
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; ++i)
{
if (str[i-1]!='0') dp[i] = dp[i-1];
int x = (str[i-2]-'0')*10+(str[i-1]-'0');
if (x<=26 && x>=10)
dp[i] += dp[i-2];
}
printf("%d\n", dp[n]);
return 0;
}
编辑于 2020-12-26 08:55:58
回复(0)
import sys line=sys.stdin.readline().strip() sum = [0 for i in range(len(line))] for i in range(len(line)): if(line[i] != '0'): x = 1 if(i==0) else sum[i-1] sum[i] += x if(i > 0 and line[i - 1] != '0' and eval(line[i-1]+line[i]) <= 26): x = 1 if(i==1) else sum[i-2] sum[i] += x print(sum[len(line)-1])
发表于 2019-08-18 21:58:44
回复(0)
/*
借鉴楼上的动态规划的想法，把规则总结得简单些；
dp[n] 为 1~n 个字符的解码方式
0.若字符串为空，或第一个字符为 '0'，直接输出0.
1.初始化：dp[0]=1; dp[1]=1; // 无字符的解码方式为1，前1个字符的解码方式为1
2.(a) 若当前字符不为 '0'：dp[j] += dp[j-1];
(b) 若当前字符和前一个字符组成的数字 tmp，满足 10<=tmp<=26，dp[j] += dp[j-2];
(c) 不满足 (a)(b) 解码条件，无法解码，退出输出 0
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>> s;
if(s[0]=='0' || s.empty()){
cout<< 0 << endl;
}else{
int sl = s.size();
vector<int> dp(sl+1, 0);
dp[0] = 1;
dp[1] = 1;
for(int i=1; i<sl; ++i){
int j = i+1;
int tmp = (s[i-1]-'0')*10 + (s[i]-'0');
if(s[i]!='0'){
dp[j] += dp[j-1];
}
if(10<=tmp && tmp<=26){
dp[j] += dp[j-2];
}
if(dp[j]==0){
dp[sl] = 0;
break;
}
}
cout<< dp[sl] << endl;
}
return 0;
}
发表于 2019-08-17 09:33:19
回复(0)
function decode(str){
//str = str.toString(); //这最好判断一下参数是否为字符串
let arr = str.split('');
if (arr.length == 1) return 1;
if (arr.length == 2){
if (parseInt(arr[0] + arr[1]) <= 26) return 2;
else return 1;
}
if (arr.slice(0,2).join('') > 26){
let newstr = arr.slice(1).join('');
return decode(newstr);
}
else{
let firststr = arr.slice(1).join('');
let secondstr = arr.slice(2).join('');
return decode(firststr) + decode(secondstr);
}
}
发表于 2019-02-15 14:40:22
回复(0)
import java.util.Scanner;
public class Main {
public static void main( String[] args ) {
Scanner sc = new Scanner( System.in );
while ( sc.hasNext() ) {
String str = sc.next();
if( str.charAt(0) == '0' ) System.out.println( 0 );
else {
int[] dp = new int[str.length()+1];
dp[0] = 1;
dp[1] = 1;
for( int i = 2; i <= str.length(); i ++ ) {
int tmp = 0;
if( str.charAt(i-1) != '0' ) tmp += dp[i-1];
int num = Integer.parseInt( str.substring(i-2,i) );
if( num > 9 && num < 27 ) tmp += dp[i-2];
if( tmp != 0 ) dp[i] = tmp;
else {
dp[str.length()] = 0;
break;
}
}
System.out.println( dp[str.length()] );
}
}
sc.close();
}
}
发表于 2019-01-23 19:27:39
回复(0)
//楼上两位太麻烦，直接dp动态规划即可
#include<iostream>
#include<vector>using namespace std;
int main()
{
string s;
cin>>s;
int n=s.size();
vector<int>dp(n+1,0);
dp[0]=1;
dp[1]=1;
for(int i=2;i<=n;i++){
int j=i-1;
if(s[j-1]>'2'||(s[j-1]=='2' && s[j]>'6')){
dp[i]=dp[i-1];
}
else{
dp[i]=dp[i-2]+dp[i-1];
}
}
cout<<dp[n]<<endl;
return 0;
}
发表于 2018-10-18 13:55:04
回复(1)
def numdecode(s): if len(s)==0 or s[0]=='0': return 0 if len(s)==1: return 1 num=[] for i in range(len(s)): num.append(1) if s[1]=='0' and s[0]<='2': num[1]=1 elif s[0]=='1' or (s[0]=='2' and s[1]<='6'): num[1]=2 elif s[1]=='0': num[1]=0 else: num[1]=1 for i in range(2,len(s)): if s[i]=='0' and s[i-1]<='2' and s[i-1]>'0': num[i]=num[i-2] elif s[i-1]=='1' or (s[i-1]=='2' and s[i]<='6'): num[i]=num[i-1]+num[i-2] elif s[i]=='0': num[i]=0 else: num[i]=num[i-1] return num[-1] while True: try: ss=input() res=numdecode(ss) print(res) except: break
发表于 2018-09-05 14:14:05
回复(0)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
inline int getResult(const string& num) {
auto len = num.size();
vector<int> dp;
dp.resize(len);
dp[0] = 1;
if(num[1] != '0' && ((num[0] == '2' && num[1] <= '6') || num[0] < '2') && len >= 2 && num[0] > '0' ) {
dp[1] = 2;
} else {
dp[1] = 1;
}
for(size_t i = 2; i < len; ++i) {
if(num[i] != '0' && ((num[i - 1] == '2' && num[i] <= '6') || num[i - 1] < '2') && num[i - 1] > '0') {
dp[i] = dp[i - 1] + dp[i - 2];
} else {
dp[i] = dp[i - 1];
}
}
return dp[len - 1];
}
int main() {
string num;
while(cin >> num) {
if(num.find("00") != string::npos || num[0] == '0') {
cout<<"0"<<endl;
continue;
}
auto res = getResult(num);
cout<<res<<endl;
}
return 0;
}
发表于 2018-08-20 21:19:05
回复(1)
问题信息
通过挑战的用户
查看代码-
2022-09-19 22:21:32 -
2022-08-27 19:03:19
-
2022-08-27 15:15:05 -
2022-08-26 11:42:17
-
2022-08-11 23:11:52
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
