解码_商汤科技笔试题

这个ID没人用

//商汤笔试题是真的难，限时做的话，只有大佬才做得完吧。

//解题思路：动态规划定义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)

Java

Mono_Chrome

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)

JavaScript

益明

动态规划。

这里做题为了节约时间先不考虑节约内存的建立备忘录方法，直接递归。

边际为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) {  // 判断被去掉的两位数是否大于26
	

	
		return 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)

abcabcabc

  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)

xiasun

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)

Python 3

TS9527

跳楼梯Plus版

我们考虑在下标为k处的情况：第k处的译码方案数量应该是k - 1处的译码数量 + k - 2处的译码数量（k - 1位对应只译1位的情况，即a-i，k - 2位对应只译2位的情况，即j-z）。用代码来表达就是dp[k] = dp[k - 1] + dp[k - 2]

但是，会出现以下特殊情况：

1. 第k - 1、k位均为0，即字符串中存在'00'的情况。这个时候怎么译都不行的（哪怕前面的0跟了k - 2位一起译，还会剩下一个0没法翻译），答案直接返回0就行。

2. 第k - 1位不为0（为1或2），但第k位为0。这个时候第k位必须要跟第k - 1位一起译，因此解决方案数只有第k - 1位的解决方案，即dp[k] = dp[k - 1]。

3. 第k - 1位为0，但第k位不为0。这个时候只有一种译码方法（就是a-i选一个，k - 1位的0要跟k - 2位一起译），因此此解决方案数只有第k - 1位的解决方案，即dp[k] = dp[k - 1]。

4. 第k - 1、k位合起来的数超过26了，这个时候是没有字母对应的，也译不了，因此解决方案数只有第k - 1位的解决方案，即dp[k] = dp[k - 1]。

综上所述，应有：

如果输入字符串s中有'00'，返回0

如果int(s[k - 2: k] (两端均取)) <= 10 或 == 20 或 > 26: dp[k] = dp[k - 1]

否则dp[k] = dp[k - 1] + dp[k - 2]。

跟跳楼梯类似，我们可以用一个长数组来记录每一步的结果。但是这个状态转移方程只与前两步的结果有关，可以只用一个长度为2的数组迭代，即把空间复杂度降为O(1)。

AC代码：

class MainActivity:

    def main(self):
        # Read the data
        s = input()
        if '00' in s:
            print(0)
            return
        # Initialization
        results = [1, 0 if s[0] == '0' else 1]
        # Traverse
        for ptr in range(1, len(s)):
            part = int(s[ptr - 1: ptr + 1])
            if part <= 10&nbs***bsp;part == 20&nbs***bsp;part > 26:
                results.append(results[-1])
            else:
                results.append(sum(results))
            results.pop(0)
        print(results[-1])


if __name__ == '__main__':
    M = MainActivity()
    M.main()

发表于 2024-08-26 12:16:35 回复(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)

DL3D

#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)

牛客497864927号

动态规划，注意细节

#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)

sunn4room

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)

lufeibat

//楼上两位太麻烦，直接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)

Airec

问一个问题，为什么7256224241262422162912798142114要输出7200，

我的理解是输出4608，即：2*3*2*3*2*4*2*2*4，我错在哪里了呢？

编辑于 2018-09-03 21:13:04 回复(1)

解码

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题