首页 > 试题广场 >

摩尔斯电码解码

[编程题]摩尔斯电码解码
  • 热度指数：3591 时间限制：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
算法知识视频讲解
添加回答
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)
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)
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)
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)
Java
深度卷人网络头像 深度卷人网络 
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str = br.readLine().toCharArray();
        int[] dp = new int[str.length + 1];
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 1;i < str.length;i++) {
            dp[i + 1] = dp[i];
            if (i - 1 >= 0 && str[i - 1] == '1') {
                dp[i + 1] += dp[i - 1];
            }
            if (i - 2 >= 0 && str[i - 2] == '1') {
                dp[i + 1] += dp[i - 2];
            }
        }
        System.out.printf("%d", dp[str.length]);
        return;
    }
}


发表于 2021-03-08 20:34:54 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

相关试题

摩尔斯电码解码

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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