做网站项目收获,请稍后重试(3008),中小型企业查询网站,制作excel表格全步骤1. 题目
给定一个数字#xff0c;我们按照如下规则把它翻译为字符串#xff1a; 0 翻译成 “a” #xff0c; 1 翻译成 “b”#xff0c;……#xff0c; 11 翻译成 “l”#xff0c;……#xff0c; 25 翻译成 “z”。
一个数字可能有多个翻译。请编程实现一个函数我们按照如下规则把它翻译为字符串 0 翻译成 “a” 1 翻译成 “b”…… 11 翻译成 “l”…… 25 翻译成 “z”。
一个数字可能有多个翻译。请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译
分别是bccfi, bwfi, bczi, mcfi和mzi提示
0 num 2^31来源力扣LeetCode 链接https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
动态规划类似斐波那契数列dp[i] 表示翻译第 i 位字符时的方案数dp[0] 空串方案数 1dp[1] 第一位数只有1种翻译str[i-2]1 ||(str[i-2]2 str[i-1] 5)可以2个字符翻译2个也可以合并其余情况只能单独翻译成1个
class Solution {
public:int translateNum(int num) {string str to_string(num);int i, n str.size();int dp[n1] {0};dp[0] 1;//第0个字符空串dp[1] 1;//第一个字符翻译只有1种可能for(i 2; i n; i){if(str[i-2]1 ||(str[i-2]2 str[i-1] 5))//该种情况可以把这两位数翻成1个或者2个字符dp[i] dp[i-2]dp[i-1];else//34,29只能单独翻译dp[i] dp[i-1];}return dp[n];}
};
