首页 > 试题广场 >

摩尔斯电码解码

[编程题]摩尔斯电码解码
  • 热度指数：3525 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
已知摩尔斯电码和字符映射关系如下：
  • A -> 0
  • B -> 1
  • C -> 10
  • D -> 11
  • E -> 100
  • F -> 101
  • G -> 110
  • H -> 111
当前我们获取到了一串01数字字符串，需要进行摩尔斯电码解码，请问共有多少种解码方法？

输入描述:
一行由0和1组成的字符串


输出描述:
一行一个数字表示答案，即解码方法数量
示例1

输入

11

输出

2

说明

有D和BB两种解法
示例2

输入

100

输出

3

说明

有E,BAA和CA三种解法

备注:
输入字符串长度范围为1～100
输出解码方法数不超过2147483647
算法知识视频讲解
添加回答
lambdafate头像 lambdafate
无脑dp就完事了。 温馨提示: 使用Python的话最后想着对2**32取模， 不然只能过80%左右 
source = input()
encode = {"0", "1", "10", "11", "100", "101", "110", "111"}

def solve(source):
    if len(source) <= 1:
        return len(source)
    dp = [0] * (len(source) + 1)
    dp[0], dp[1] = 1, 1
    dp[2] = 1 + (1 if source[:2] in encode else 0)
    for i in range(3, len(dp)):
        for j in range(3):
            k = i - j - 1
            if source[k:i] in encode:
                dp[i] += dp[k]
    return dp[-1] % 2**32

print(solve(source))


发表于 2021-01-21 11:46:31 回复(3)
人海追风头像 人海追风
抄的😨😨
#include<iostream>
#include<vector>
using namespace std;

int main()
{
    string s;
    while(cin>>s);
    int n = s.size();
    vector<int> dp(n+1, 0);
    dp[n] = 1;
    for(int i=n-1;i>=0;i--)
    {
        dp[i] = dp[i+1];    //第一种情况， s[i]单独解码
        if(s[i]=='1')
        {
            if(i+1<n)    {dp[i] += dp[i+2];}
            if(i+2<n)    {dp[i]+= dp[i+3];}
        }
    }
    cout<<dp[0]<<endl;
    return 0;
}

发表于 2021-01-06 09:40:10 回复(0)
一只菜鸡罢了头像 一只菜鸡罢了 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        String text = scanner.nextLine();
        int n=text.length();
        String[] words=new String[]{"0","1","10","11","100","101","110","111"};
        long[] dp=new long[n+1];
        dp[0]=1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < words.length; j++) {
                if(text.substring(0,i).endsWith(words[j])){
                    dp[i]+=dp[i-words[j].length()];
                }
            }
        }
        System.out.println(dp[n]);
    }
}
我就说为啥只过了41/50，原来超出int范围了

发表于 2022-08-20 11:39:52 回复(0)
pein531头像 pein531
动态规划求解，注意当遇到字符'1'的时候，有三种翻译的方式 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str = br.readLine().toCharArray();
        int n = str.length;
        int[] dp = new int[n + 1];
        dp[n] = 1;         // 最后一个字符肯定只能是一种翻译
        // 从后往前遍历字符
        for(int i = n - 1; i >= 0; i--){
            dp[i] = dp[i + 1];     // 单字符码的情况
            if(str[i] == '1'){      // 对于"1"，还有双字符码和三字符码的情况
                if(i + 2 <= n) dp[i] += dp[i + 2];
                if(i + 3 <= n) dp[i] += dp[i + 3];
            }
        }
        System.out.println(dp[0]);
    }
}


发表于 2021-01-20 23:00:33 回复(5)
飞哥011头像 飞哥011
这个题贼***,他样例11110110100111011001111100101010110011110111001000的时候会成为负数-871755317,所以你如果怕超int,你用long型得到正数反而错了,只会50个过41,41/50
发表于 2021-11-09 09:16:28 回复(0)
Java
kobeaaa头像 kobeaaa 
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int length = str.length();
        int[] dp = new int[length+2];
        for(int i=0;i<length+2;i++) dp[i]=0;
        for(int i=0;i<length;i++){
            if (i==0){
                dp[i] = 1;
                if("1".equals(str.substring(i,i+1))){
                    dp[i+1] += 1;
                    dp[i+2] += 1;
                }
            }else{
                dp[i] += dp[i-1];
                if("1".equals(str.substring(i,i+1))){
                    dp[i+1] += dp[i-1];
                    dp[i+2] += dp[i-1];
                }
            }
            
        }
        System.out.println(dp[length-1]);
    }
}

发表于 2021-08-20 14:03:34 回复(0)
0x3f3f头像 0x3f3f 
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    int n = s.size();
    if(n==0){
        cout<<0;
        return 0;
    } 
    int dp[n+1];
    memset(dp,0,sizeof(dp));
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        if(i>=1) dp[i]+=dp[i-1];
        if(i>=2&&s[i-2]=='1') dp[i] += dp[i-2];
        if(i>=3&&s[i-3]=='1') dp[i] += dp[i-3]; 
    }
    cout<<dp[n];
    return 0;
}

发表于 2022-02-22 22:46:24 回复(0)
牛客598416696号头像 牛客598416696号
/*
 * 思路：动态规划
 * 难点在于如何构造状态转移方程：
 * dp[i] 表示s[0] - s[i]的子串的解法
 * dp[0] = 1
 * dp[1] = 2
 * dp[i] = dp[i - 1] + 
           s[i- 1:i]与s[i]相同 ? 0 : dp[i - 2] +
           s[i -3 : i]与(s[i] || s[i - 1: i])相同 ？ 0 ：dp[i-3]
 */

#include <iostream>
#include <string>
#include <vector>

using namespace std;
int main() {
    string line;
    cin >> line;
    int len = line.size();
    vector<int> dp(len);
    for (int i = 0; i < len; i++) {
        if (i == 0) {
            dp[i] = 1;
        }
        if (i > 0) {
            dp[i] = dp[i - 1];
            if (line.substr(i - 1, 1) != "0" ) {
                dp[i] += (i > 1 ? dp[i - 2] : 1);
            }
        }
        if (i > 1) {
            if (line.substr(i - 2, 1) != "0") {
                dp[i] += (i > 2 ? dp[i - 3] : 1);
            }
        }
    }
    cout << dp[len - 1] << endl;
    
    return 0;
}

发表于 2022-01-15 21:05:23 回复(0)
渴望wlb的垂耳兔很感性头像 渴望wlb的垂耳兔很感性
用js要在每次做加法后要取模Math.pow(2, 31) 
function getSolveCount(str) {
    const dp = Array(str.length + 1);
    dp[0] = 1;
    dp[1] = 1;
    const MAX_VALUE = 2147483647 + 1;
    for (var i = 2; i < dp.length; i++) {
        dp[i] = dp[i - 1];
        dp[i] = dp[i] % MAX_VALUE;
        if (str[i - 2] !== "0") {
            dp[i] += dp[i - 2];
            dp[i] = dp[i] % MAX_VALUE;
        }
        if (i >= 3 && str[i - 3] !== "0") {
            dp[i] += dp[i - 3];
            dp[i] = dp[i] % MAX_VALUE;
        }
    }
    return dp[str.length];
}

const str = readline();
const res = getSolveCount(str);
print(res);
发表于 2021-09-04 20:38:34 回复(0)
JavaScript
DreamYao-66头像 DreamYao-66 
const str = readline()
const towArr = ["10","11"]
const threeArr = ["100","101","110","111"]
const dp = new Array(str.length);
dp[0] = 1
dp[1] = 1
for(let i = 2; i<=str.length;i++){
    dp[i] = dp[i-1]
    if(towArr.indexOf(str.substring(i-2,i))!== -1) 
        dp[i] = dp[i]+dp[i-2]
    if(i>2 && threeArr.indexOf(str.substring(i-3,i))!==-1)
        dp[i] = dp[i] + dp[i-3]
}
console.log(dp[str.length])
通过率：41/50
dp解法
发表于 2021-08-30 23:27:04 回复(0)
tsrj头像 tsrj 
package _12月在家重刷.题目;

import java.util.*;

/**
 * @author qxm
 * @create 2023-03-06 17:44
 **/
public class T30摩尔斯电码解码 {
    //1:dp
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        long[] dp = new long[str.length()];//dp[i]:i到str.len-1的子字符串有dp[i]种解密方式
        dp[str.length() - 1] = 1;
        for (int i = str.length() - 2; i >= 0; i--) {
            dp[i] = dp[i + 1];
            if (str.charAt(i) == '1') {
                if (i + 1 < str.length()) {
                    if (i + 2 == str.length()) {
                        dp[i]++;
                    } else {
                        dp[i] += dp[i + 2];
                    }
                }
                if (i + 2 < str.length()) {
                    if (i + 3 == str.length()) {
                        dp[i]++;
                    } else {
                        dp[i] += dp[i + 3];
                    }
                }
            }
        }
        System.out.println(dp[0]);
    }

    //2:回溯超时G(但是如果要求所有的解密结果，必须要回溯)
    static Map<String, String> map = new HashMap<>();
    //static List<String> path = new ArrayList<>();
    static int ans = 0;

    public static void main1(String[] args) {
        map.put("0", "A");
        map.put("1", "B");
        map.put("10", "C");
        map.put("11", "D");
        map.put("100", "E");
        map.put("101", "F");
        map.put("110", "G");
        map.put("111", "H");
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        backtracking(0, str);

        System.out.println(ans);
    }

    public static void backtracking(int index, String arr) {
        if (index > arr.length()) {
            return;
        }
        if (index == arr.length()) {
            ans++;
            //System.out.println(path);
            return;
        }
        for (int i = 0; i <= 2 && index + i <= arr.length() - 1; i++) {
            String sub = arr.substring(index, index + i + 1);
            if (map.containsKey(sub)) {
                //path.add(sub);
                backtracking(index + i + 1, arr);
                //path.remove(path.size() - 1);
            }
        }
    }

}

发表于 2023-03-06 18:26:43 回复(0)
Java
莫茗丶头像 莫茗丶 
import java.util.Scanner;

public class Main {
   
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String code=sc.nextLine();
        System.out.println(deCode(code));
    }

    private static long deCode(String code) {
        char[]  codes=code.toCharArray();
        int n=codes.length;
        long[] dp=new long[n+1];
        //注意初始化为1种
        dp[0]=1;
        
        dp[1]=1;dp[2]=codes[0]=='0'?1:2;
        for (int i = 3; i < n+1; i++) {
            dp[i]=dp[i-1];
            if(codes[i-2]=='1'){
                dp[i] += dp[i-2];
            }
            if(codes[i-3]=='1'){
                dp[i] += dp[i-3];
            }
        }
        return dp[n];
    }

}

编辑于 2022-09-04 12:14:53 回复(0)
ShallweZhuang头像 ShallweZhuang
动态规划问题
1. 编码规律1开头的有三种情况（分位数讨论）
2. 因为是编码，所以后面的会影响前面的，所以应该从后往前 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();
        in.close();
        line = new StringBuilder(line).reverse().toString();        // 将字符串进行翻转这样就比较直观
        long[] dp = new long[line.length() + 1];                    // dp[i]代表长度为 i 产生的编码数 - long数组防止溢出
        dp[0] = 0;                                                  // 长度为0的字符串产生编码种类为 0
        dp[1] = 1;                                                  // 长度为1的字符串产生编码种类为 1
        for (int i = 2; i <= line.length(); i++) {                  // 从长度为2开始迭代
            char c = line.charAt(i - 1);
            dp[i] = dp[i - 1];
            if (c == '1') {
                if(i - 2 >= 0) dp[i] += dp[i - 2];
                if(i - 3 >= 0) dp[i] += dp[i - 3];
            }
        }
        System.out.println(dp[line.length()]);
    }

}



发表于 2022-08-13 19:06:15 回复(0)
Python 3
Patrick027头像 Patrick027
测试数据有问题，测试数据没考虑int的越界。
测试用例 111101101001110110011111001010101100111101110010001111011110
会造成数据越界，用64位的整数可以算出来正确结果是1520481317175
但是OJ的标准答案的结果是62894391
python 代码：
text = input()
dp = [0 for i in text]
dp[0] = 1
for i in range(1, len(text)):
    dp[i] += dp[i - 1]
    if text[i - 1] == '1':
        dp[i] += dp[i - 2] if i >= 2 else 1
    if i >= 2 and text[i - 2] == '1':
        dp[i] += dp[i - 3] if i >= 3 else 1
print(dp[-1])

发表于 2022-04-16 01:10:22 回复(1)
Java
牛客469515011号头像 牛客469515011号
动态规划，设dp[i]表示输入字符串长度为i+1时的解码方法数。
index=i时；
1、因为可以看作在i-1的字符串上加单个字符，解码方法数和原先一样，必有dp[i]+=dp[i-1]，即在index=i-1时的解码方法数；
2、如果index=i-1时是'1'，可以看作在i-2的字符串上加两个字符，dp[i]+=dp[i-2]
3、如果index=i-2时是'1'，可以看作在i-3的字符串上加三个字符，dp[i]+=dp[i-3]
需要满足i-3>=0，i>=3
先列出dp[i]，i=0、1、2的初始化。 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        char[] list = scanner.next().toCharArray();
        System.out.println(Main.count(list)+"");
    }
    static int count(char[] list){
        int[] dp=new int[list.length];
        dp[0]=1;
        if(list.length==1) return dp[0];
        dp[1]= list[0]=='1'? 2:1;
        if(list.length==2) return dp[1];
        dp[2]=dp[1];
        if(list[0]=='1') dp[2]+=1;
        if(list[1]=='1') dp[2]+=dp[0];
        for(int i=3;i<list.length;++i){
            dp[i]=dp[i-1];
            if(list[i-1]=='1') dp[i]+=dp[i-2];
            if(list[i-2]=='1') dp[i]+=dp[i-3];
        }
        return dp[list.length-1];
    }
}


发表于 2022-04-14 10:57:50 回复(0)
JavaScript
WZXA头像 WZXA 
var s=readline();
console.log(fn(s));

function fn(s){
    var n=s.length;
    var dp=new Array(n+2).fill(1);
   
    for(let i=n-1;i>0;i--){
        dp[i]=dp[i+1];
        if (s[i-1]=='1'){
            if (i+2<=n+1) dp[i]+=dp[i+2];
            if (i+3<=n+1) dp[i]+=dp[i+3];
        }
        dp[i]=dp[i]%Math.pow(2,32);
    }
    return dp[1]
}

发表于 2022-04-07 17:26:32 回复(1)
代码需要写注释？头像 代码需要写注释？
这题是我见过最***的题，原来不超过int最大值是这个意思，完全不按照正常逻辑走，脑残体 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static Map<String, Character> m = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        m.put("0", 'A');
        m.put("1", 'B');
        m.put("10", 'C');
        m.put("11", 'D');
        m.put("100", 'E');
        m.put("101", 'F');
        m.put("110", 'G');
        m.put("111", 'H');
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 1; i < s.length(); i++) {
            int k = i - 1, l = i - 2;
            dp[i + 1] = dp[i];
            String substring = s.substring(k, i + 1);
            Character character = m.get(substring);
            if (character != null)
                dp[i + 1] += dp[i - 1];
            if (l > -1) {
                String str = s.substring(l, i + 1);
                Character c = m.get(str);
                if (c != null)
                    dp[i + 1] += i - 2 > 0 ? dp[i - 2] : 1;
            }
        }
        System.out.println(dp[s.length()]);
    }
}

发表于 2022-03-29 17:28:59 回复(1)
新世纪热心网友头像 新世纪热心网友
PYTHON 
arr = list(int(n) for n in input())
n = len(arr)
res = [0 for x in range(0,n+1)]
res[-1] = 1
for i in range(n-1,-1,-1): #从后往前
    res[i] = res[i+1]
    if arr[i] == 1:  #单字节码
        if i + 2 <= n:
            res[i] += res[i + 2]
        if i + 3 <= n:
            res[i] += res[i + 3]
             
#这个地方如果不取模过不了样例，41/50.感觉应该是解法已经超过2^32了，超出int类型，判断出问题了
print(res[0] % 2**32 )

发表于 2022-03-19 10:53:53 回复(0)
Java
甲甲子头像 甲甲子

第一想法递归，但超时了；
之后看到的是动态，马上就明白（就是一道标准dp问题）
遍历到str[i]时，考虑i,i-1,i-2的情况

注意点：
  •     i肯定是有效的（str只由0,1组成且0,1都可以）；
  •     i-1，i-2考虑边界问题
【思路上没有任何障碍】 
importjava.util.HashMap;
importjava.util.HashSet;
importjava.util.Scanner;
 
 
publicclassMain{
 
    publicstaticvoidmain(String[] args) {
        Scanner scanner =newScanner(System.in);
        String str = scanner.next();
        HashSet<String> res =newHashSet<>();
        // 0,1不用加
        res.add("10");
        res.add("11");
        res.add("100");
        res.add("101");
        res.add("110");
        res.add("111");
        int[] dp =newint[str.length()];
        dp[0] =1;
        for(inti =1; i < str.length(); i++) {
            dp[i] = dp[i -1];
            if(res.contains(str.substring(i -1, i +1))) {
                dp[i] += i -2>=0? dp[i -2] :1;
            }
            if(i -2>=0&& res.contains(str.substring(i -2, i +1))) {
                dp[i] += i -3>=0? dp[i -3] :1;
            }
        }
        System.out.println(dp[str.length()-1]);
    }
}


编辑于 2021-08-20 12:08:28 回复(0)
未来万事顺意头像 未来万事顺意
动归，一开始只通过80%，看评论说需要%2^32，因为题目中限制了输出最大值，但是取模之后，通过率仍不是100%，而是96%，不知道为啥了，代码思路应该没啥问题 
let str = readline();
print(codeNums(str))

function codeNums(str) {
    let dic = new Map();
    dic.set('0', 'A');
    dic.set('1', 'B');
    dic.set('10', 'C');
    dic.set('11', 'D');
    dic.set('100', 'E');
    dic.set('101', 'F');
    dic.set('110', 'G');
    dic.set('111', 'H');
    let dp = new Array(str.length);
    dp[0] = 1;
    dp[1] = str[0] === '0' ? 1 : 2;
    for (let i = 2; i < str.length; i++) {
        let str1 = str.slice(i - 1, i + 1);
        let str2 = str.slice(i - 2, i + 1);
        dp[i] = dp[i - 1] + (dic.has(str1) ? dp[i - 2] : 0);
        if (dic.has(str2)) {
            dp[i] += (i >= 3 ? (dp[i - 3]) : 1);
        }

    }
    return dp[str.length - 1] % Math.pow(2, 31);
}

编辑于 2021-08-30 21:25:43 回复(3)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 网易 游戏研发工程师 2021 大数据开发工程师 Java工程师
上传者：小小
难度：
26条回答 6786浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号