首页 > 试题广场 >

把数字翻译成字符串

[编程题]把数字翻译成字符串
  • 热度指数：151641 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。

现在给一串数字，返回有多少种可能的译码结果

数据范围：字符串长度满足 0 < n \leq 90
进阶：空间复杂度 ，时间复杂度
示例1

输入

"12"

输出

2

说明

2种可能的译码结果（”ab” 或”l”）
示例2

输入

"31717126241541717"

输出

192

说明

192种可能的译码结果
算法知识视频讲解
添加回答
C
一个优雅的程序猿头像 一个优雅的程序猿 
int solve(char* nums ) {
    int numsLen = strlen(nums);
    if(numsLen<1)
        return 0;
    else if(numsLen<2) {
        if(nums[0]>='1' && nums[0]<='9')
            return 1;
        else
            return 0;
    }
    else if(numsLen<3) {
        int val = (nums[0]-'0')*10+(nums[1]-'0');
        if(val<=9)
            return 0;
        else if(val%10==0) {
            if(val==10 || val==20)
                return 1;
            else
                return 0;
        }
        else if(val<=26)
            return 2;
        else 
            return 1;
    }
    else {
        if(nums[1]=='0') {
            if(nums[0]>='3')
                return 0;
            else if(nums[0]=='0')
                return 0;
            else
                return solve(nums+1);
        }
        else if(nums[1]<'7') {
            if(nums[0]>='3' || nums[0]=='0')
                return solve(nums+1);
            else
                return solve(nums+1)+solve(nums+2);
        }
        else {
            if(nums[0]>='2' || nums[0]=='0')
                return solve(nums+1);
            else
                return solve(nums+1)+solve(nums+2);
        }
    }
}

发表于 2024-03-24 12:11:01 回复(0)
C
深情的袋鼠求你们别卷了头像 深情的袋鼠求你们别卷了

/**
 * 解码
 * @param nums string字符串 数字串
 * @return int整型
 */
#include <stdio.h>
#include <string.h>

int get_cnt(char* s);
int get_num(char* s) {
    return (s[0] - '0') * 10 + (s[1 ] - '0');
}

int get_cnt(char* s) {
    int i = get_num(s);
    // printf("i = %d  ", i);
    if (i == 0) {
        return 0xff;
    }
    if (i < 10) {
        return 1;
    }
    if (i == 10 || i == 20) {
        return  1;
    }
    if (i < 27) {
        return 2;
    }
    if (i  % 10 == 0 ) {
        return 0xff;
    }
    return 1;
}

#define max(a,b) ((a) > (b)) ? (a) :(b)
int solve(char* nums ) {
    // write code here

    int s[strlen(nums)];
    s [0] = 1;

    if (nums[0] == '0') {
        return 0;
    }

    if (strlen(nums) == 1) {
        return 1;
    }

    int j = get_num(&nums[0]);
    if (j > 26 && j < 30) {
        s[1] = 1;
    } else if (j == 10 || j == 20) {
        s[1] = 1;
    } else if ( j <= 26) {
        s[1] = 2;
    } else {
        s[1] = 1;
    }
    if (strlen(nums) == 2) {
        return s[1];
    }

    for (int i = 2; i < strlen(nums); i++) {
        int k = get_cnt(&nums[i - 1]);
        if (k == 0xff) {
            return 0;
        }
        if (k == 1) {
            s[i] = s[i - 1];
        }
        if (k == 2) {
            s[i] = s[i - 2] + s[i - 1];
        }
        if(j == 3)
        {
            s[i] = s[i - 2];
        }
    }
    printf("%d", s[strlen(nums) - 1]);
    return s[strlen(nums) - 1];
}
发表于 2023-04-05 15:30:31 回复(0)
C
牛客579577851号头像 牛客579577851号
int Method1(char str[],int start,int number){
    int dp[100] ={0};
    dp[number] = 1;
    for(int i = number - 1;i >= 0;i--){
        if(str[i] != '0') {
        dp[i] = dp[i + 1];
        if(str[i + 1]&& ((str[i] - '0') * 10 + str[i + 1] - '0' < 27)){//后面还有数字，并且第一位为1，因为当start位为2 ~ 9时都已不符合题意 
            dp[i] += dp[i + 2];
            }
        }
    }
    return dp[start];
}
int solve(char* nums ) {
    // write code here
    int number = strlen(nums);
    return Method1(nums, 0, number + 1);
}
发表于 2022-12-13 13:11:20 回复(0)
提交观点

问题信息

动态规划
上传者：牛客332641号
难度：
3条回答 4926浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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