题目：
题解
- 解题总统思路：
1、字符串遍历
解题思路：为方便获取数字的各位 xi，考虑先将数字 num 转化为字符串 s ，通过遍历 s 实现动态规划
复杂度分析：
- 时间复杂度 O(N) ： N 为字符串 s 的长度（即数字 num 的位数 log(num) ），其决定了循环次数。
- 空间复杂度 O(N) ： 字符串 s 使用 O(N)大小的额外空间。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20// 字符串遍历
public class Solution {
public int translateNum(int num) {
// 首先将num变成字符串
String s = String.valueOf(num);
// 设置 b“无数字” 和 a“第 1 位数字” 的翻译方法数量均为 1
int a = 1,b = 1;
// 从后往前循环，计算翻译方法的数量
for (int i = s.length() - 2; i > -1 ; i--) {
// 取到 i+2 的前两个数字
String tmp = s.substring(i, i + 2);
// 判断这俩个数字组合以后ASCII码差值是否在10~25之间
int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a;
b = a;
a = c;
}
return a;
}
}
2、数字求余（降低空间复杂度O(n)–>O(1)）
解题思路：利用求余运算 num % 10 和求整运算 num / 10 ，可获取数字 num 的各位数字（获取顺序为个位、十位、百位…）。
复杂度分析：
- 时间复杂度 O(N) ： N 为字符串 s 的长度（即数字 num 的位数 log(num) ），其决定了循环次数。
- 空间复杂度 O(N) ： 几个变量使用常数大小的额外空间。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22// 数字求余
class Solution2 {
public int translateNum(int num) {
// 设置 b“无数字” 和 a“第 1 位数字” 的翻译方法数量均为 1，x十位，y个位
int a = 1,b = 1,x,y = num % 10;
// 从后往前循环，计算翻译方法的数量
while (num != 0) {
// 拿到x的值
num /= 10;
x = num % 10;
// 总值
int tmp = x * 10 + y;
// 判断这俩个数字组合以后是否在10~25之间
int c = tmp >= 10 && tmp <= 25 ? a + b : a;
b = a;
a = c;
y = x;
}
return a;
}
}