前言
又是好久没有更新了
正文
问题来源
本问题来自leetcode上的面试题46题。
问题描述
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
分析：
递归的思想
首先将数字转为[]byte类型，当处理发现slice的长度为0时，则代表已经有一种可能的情况了（返回1即可），当slice长度为大于0时，则可以直接加上递归slice[1:]后面的结果，当slice长度大于1时（可进行两位），则需要判断开头的数值是否小于25并且首位不为0后，可以直接加上递归slice[2:]后面的结果.
func translateNum(num int) int {
b := []byte(strconv.Itoa(num))
return translate(b)
}
func translate(b []byte) int {
ret := 0
if len(b) == 0 {
return 1
}
if len(b) > 0 { //此判断有些多余
ret += translate(b[1:])
}
if len(b) > 1 && (b[0] == '1' || (b[0] == '2' && b[1] < '6')) {
ret += translate(b[2:])
}
return ret
}
根据题目描述, 它很像一道动态规划经典题: 爬楼梯, 也是 1 个数字可以有多种方案
不同的是这里可以组成两位数的数字是有限制的, 不能像爬楼梯那样无脑相加
所以我们可以定义 dp 数组, dp[i]表示从左到右遍历到第 i 位数字时可以翻译成的字符串数目
固定第 i 位数字后, 观察其前一位数字, 可以得到如下转移方程:
如果当前数字和前一位数字(如果存在的话)组成的两位数在 10 到 25 之间, 那么当前数字既可以独立使用, 也可以和之前数字合用, 所以 dp[i] = dp[i-2]（使用2个字符） + dp[i-1]（使用1个字符）
如果当前数字无法和前一位数字组成有效的两位数, 意味着当前数字只能独立使用, 所以 dp[i] = dp[i-1]
观察上述方程, 我们发现整个 dp 数组只用到了 i-2 和 i-1, 所以我们可以只使用两个变量, 定义上一个和当前的 dp 值, 这样既节省了空间, 又精简了代码
注意需要先把输入的数字转换成字符串, 方便每一位的处理
注意初始化值都为 1, 因为至少可以转换成 1 个字符串
class Solution {
public:
int translateNum(int num) {
int pre = 1, cur = 1;
string s = to_string(num);
for (int i = 1; i < s.size(); ++i) {
int value = stoi(s.substr(i-1, 2));
int temp = pre;
pre = cur;
if (value >= 10 && value <= 25) {
cur = temp + cur;
}
}
return cur;
}
};
总结：
勤思考。
结语
不管怎么样好好加油。
