给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。如输入: 12258 输出: 5
给定一个数字,从个位数即最右边开始遍历,遍历第一位时,肯定只有一种翻译方法。在遍历十位数时,就需要考虑,十位数和个位数是单独一个数字翻译成一个字符,还是十位数和个位数组合在一起翻译成一个字符。如果是各自翻译成一个字符,则只要求十位数不为0即可,若十位数为0,则方法数和只有个位数一个数字翻译成字符的方法数是一样的,即都是1.如果是十位数和个位数组合一起翻译成一个字符,则要求十位数为1,则个位数不限,或十位数为2,个位数为必须小于6,这样才能拼成一个字符。定义两个变量dp1,dp2,分别表示前一个数翻译成的字符方法数、前两个数字翻译成的方法数(如遍历到百分位时,则前一个数字为十分位数字,前两个数字为个位数),默认状态dp1,dp2均为1.一次遍历完成后,需要先将dp1赋值给dp2,再讲当前位数翻译的字符串方法数赋值为dp1,因此这里还需要一个变量count,用来记录遍历当前位数字时,可以翻译成字符串的方法数量。
package learnproject.offer;
/*
* 46.把数字翻译成字符串
*/
public class Demo46 {
/*
* 1.当遍历到某一个数字时,要分两种方式考虑:
* 1.1 该数字单独翻译成一个字符
* 1.2 该数字和前面的数字一起翻译成一个字符
* 1.2.1 要求前面一位数字不能为0
* 1.2.1 该数字要小于或等于5
* 2.采用动态规划算法,定义两个变量dp1,dp2,
* 分别表示一个数字和两个数字翻译成字符的方法数,对应前1个、2个翻译的方法数
*/
public int translateNum(int num) {
if (num < 10) {
return 1;
}
int value = 1;
int dp1 = 1;
int dp2 = 1;
while (num > 0) {
int count = 0;
int temp = num % 10; //求模运算
value = num / 10;
int valuetemp = value % 10;
num = value;
if (valuetemp == 0) {
count = dp1;
} else {
if (valuetemp == 1 || (valuetemp == 2 && temp < 6)) {
count = dp1 + dp2;
} else {
count = dp1;
}
}
dp2 = dp1;
dp1 = count;
}
return dp1;
}
public static void main(String args[]) {
Demo46 demo = new Demo46();
System.out.println(demo.translateNum(12258));
}
}