此题中将 0翻译为‘a’…25翻译为’z’ ，计算给定数字有多少种翻译方式。
思路：从第一位开始可以走一步，也可以走两步，使用递归解决，非常清晰，美中不足的是这样递归中会出现重复计算。
/** *Copyright @ 2019 Zhang Peng. All Right Reserved. *Filename: *Author: Zhang Peng *Date: *Version: *Description: **/ #include<iostream> #include<string> using namespace std; int coutnum(string & number) { //剑指offer书上的 int length = number.length(); int * counts = new int[length]; int count = 0; for (int i = length - 1; i >= 0; --i) { count = 0; if (i < length - 1) count = counts[i + 1]; else count = 1; if (i < length - 1) { int digit1 = number[i] - '0'; int digit2 = number[i + 1] - '0'; int converted = digit1 * 10 + digit2; if (converted >= 10 && converted <= 25) { if (i < length - 2) count += counts[i + 2]; else count += 1; } } counts[i] = count; } count = counts[0]; delete[] counts; return count; } int check(string & number) { int num = 10 *(number[0]-'0') + (number[1]-'0'); if (num >= 10 && num <= 25) return 1; else return 0; } int coutnum2(string & number) { //递归 int num_size = number.size(); if (num_size == 1) return 1; else if(num_size == 2) { int num = 10 * (number[0] - '0') + (number[1] - '0'); if (num >= 10 && num <= 25) return 2; else return 1; } else { string str1 = number.substr(1, num_size - 1); string str2 = number.substr(2, num_size - 2); string str3 = number.substr(0,2); //需检查是否符合要求 /*cout << num_size << endl; cout << str1 << " " << str2 << " " << str3 << endl;*/ return coutnum2(str1) + coutnum2(str2)*check(str3); } } int translator(int number) { if (number < 0) return 0; string numstr = to_string(number); return coutnum(numstr); } int translator2(int number) { if (number < 0) return 0; string numstr = to_string(number); return coutnum2(numstr); } int main() { cout << translator(12) << endl; cout << translator2(12) << endl; system("pause"); return 0; }运行结果如图： 增加非递归实现如下：
int coutnum3(string & number) { //非递归 int len = number.size(); if (len == 0) return 0; int result = 0; vector<int> count(len, 0); for (int i = len - 1; i >= 0; i--) { if (i == len - 1) count[i] = 1; else { count[i] = count[i + 1]; //默认count[i] = count[i + 1] 如果i 和i+1能翻译成字符串，则需要加上特殊的处理 string str = number.substr(i, 2); if (check(str) )//需检查是否符合要求 { if (i + 2 < len) count[i] += count[i + 2]; //i后第二位有数字，需加上count[i+2] else count[i] += 1; //i后第二位无数字，只需要加上1，即i i+1这两个字符翻译的组合 } } } result = count[0]; return result; }