文章目录
- Leetcode 面试题46. 把数字翻译成字符串
- 问题描述
- 解题报告
- 实现代码
- Leetcode 91. 解码方法
- 问题描述
- 解题报告
- 实现代码
- 参考资料
Leetcode 面试题46. 把数字翻译成字符串
问题描述
给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。
输入: 12258
输出: 5
解释: 12258有5种不同的翻译,分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”
解题报告
dp[i]dp[i]dp[i] 表示num
中从第 1
位到第i
位的翻译方法数。
则第 i
位可以单独成一位,或者和第i-1
进行组合【此时第i-1
位和第i
位组成的数字需要在[10,25]范围内】。
即:dp[i]=dp[i−1]+dp[i−2]∗okdp[i]=dp[i-1]+dp[i-2]*okdp[i]=dp[i−1]+dp[i−2]∗ok,
ok
表示第i-1
位和第i位组成的数字是否在[10,25]范围内,是则为1,不是则为0。
具体实现有递归和动规。
实现代码
- 递归
class Solution {
public:int translateNum(int num) {if(num<10){return 1;}int res=translateNum(num/10),last=num%100;if(last>=10&&last<=25)res+=translateNum(num/100);return res;}
};
- 动态规划
class Solution{public:int translateNum(int num){string s=to_string(num);int n=s.size();vector<int>dp(n+1);dp[0]=1;for(int i=1;i<=n;i++){dp[i]=dp[i-1];if(i>1){int t=stoi(s.substr(i-2,2));if(t>=10&&t<=25){dp[i]+=dp[i-2];}}}return dp[n];}
};
Leetcode 91. 解码方法
问题描述
一条包含字母 A-Z 的消息通过以下方式进行了编码:
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串,请计算解码方法的总数。
示例 1:
输入: “12”
输出: 2
解释: 它可以解码为 “AB”(1 2)或者 “L”(12)。
解题报告
与上一题有细微差别。当前为为 0
时,如果上一位取值不为 1
且不为 2
则当前位无法与任何位进行组合,直接返回 0
,否则,当前位与上一位组合。
其他方面和上一题一样。
实现代码
class Solution{public:int numDecodings(string s) {if (s[0] == '0') return 0;int n=s.size();vector<int>dp(n+1);dp[0]=1;dp[1]=1;for(int i=2;i<=n;i++){if(s[i-1]=='0'){if(s[i-2]=='1'||s[i-2]=='2') dp[i]=dp[i-2];else return 0;}else{dp[i]=dp[i-1];int t=stoi(s.substr(i-2,2));if(t>=11&&t<=26) dp[i]+=dp[i-2];}}return dp[n];}
};
参考资料
[1] Leetcode 面试题46. 把数字翻译成字符串
[2] Leetcode 91. 解码方法