题目
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
1
2
3
| 输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
|
提示：
解法一：动态规划
思路:
有点青蛙游戏，还有阶梯游戏
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int translateNum(int num) {
string nums = to_string(num);
if(nums.size() == 1)return 1;
vector<int> dp(nums.size());
dp[0] = 1;
dp[1] = ("10"<=(nums.substr(0, 2)) && (nums.substr(0, 2))<="25") ?2:1;
for(int i = 2;i<nums.size();i++){
if("10"<=(nums.substr(i-1, 2)) && (nums.substr(i-1, 2))<="25"){
dp[i] = dp[i-1] + dp[i-2];
}else{
dp[i] = dp[i-1];
}
}
return dp[nums.size()-1];
}
};
|
结果
1
2
3
4
5
6
7
8
9
10
| 执行用时：
0 ms
, 在所有 C++ 提交中击败了
100.00%
的用户
内存消耗：
5.9 MB
, 在所有 C++ 提交中击败了
25.94%
的用户
|
优化一下下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int translateNum(int num) {
string nums = to_string(num);
if(nums.size() == 1)return 1;
int l= 1;
auto temp = nums.substr(0, 2);
int r = ("10"<=temp && temp <="25") ?2:1;
int q = r;
for(int i = 2;i<nums.size();i++){
auto temp = nums.substr(i-1, 2);
if("10"<=temp && temp<="25"){
q = l + r;
}else{
q = r;
}
l = r;
r = q;
}
return q;
}
};
|
结果
1
2
3
4
5
6
7
8
9
10
11
12
| 执行用时：
0 ms
, 在所有 C++ 提交中击败了
100.00%
的用户
内存消耗：
5.8 MB
, 在所有 C++ 提交中击败了
58.65%
的用户
通过测试用例：
49 / 49
|
