当前位置：首页 > news >正文

【LeetCode】剑指 Offer（23）

news 2025/8/24 23:01:30

题目：剑指 Offer 46. 把数字翻译成字符串 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过啦！！！

写在最后：

题目：剑指 Offer 46. 把数字翻译成字符串 - 力扣（Leetcode）

题目的接口：

class Solution {
public:int translateNum(int num) {}
};

解题思路：

这道题我的的思路是使用动态规划，

并且，这道题更像是一个斐波那契数列的变式，

具体思路如下：

题目给我们传的是一个数字，

为了方便的解题，我们将数字转换成字符串

（不然到时候要用的时候还得取模之类的一系列操作，比较麻烦和难理解）

然后我们创建一个用来进行动态规划的数组dp，

dp[0] = 1，dp[1] = 1；

遍历字符串，

如果上一个字符与当前字符组成的数字 >9 且 <26

当前数字就会有两种情况：

1. 当前数字独立于前面数字，那翻译的方法就有dp[i - 1]个；

2. 当前数字与前一个数字组合，那翻译方法就有dp[i - 2]个；

所以dp[i] 就是dp[i - 1] + dp[i - 2]。

如果上一个字符与当前字符组成的数字 <9 或者 >26

只有当前数字独立于前面数字一种情况，那dp[i] == dp[i - 1]。

例：

然后遍历字符串：

继续遍历：

继续走：

因为：上一个字符与当前字符组成的数字 <9 或者 >26

这就是大致的思路，

接下来看代码：

代码：

class Solution {
public:int translateNum(int num) {//将数字转换为字符串string s = to_string(num);//建立一个动态规划的数组vector<int> dp(s.size() + 1);dp[0] = 1;dp[1] = 1;//遍历字符串for(int i = 2; i < dp.size(); i++){//如果上一个字符与当前字符组成的数字 >9 && <26if((s[i - 2] -'0') * 10 + (s[i - 1] - '0') < 26 && (s[i - 2] -'0') * 10 + (s[i - 1] - '0') > 9){//1.当前数字独立于前面数字，那翻译的方法就有dp[i - 1]个//2.当前数字与前一个数字组合，那翻译方法就有dp[i - 2]个//所以dp[i] 就是dp[i - 1] + dp[i - 2]dp[i] = dp[i - 2] + dp[i - 1];}else//如果上一个字符与当前字符组成的数字 <9 或者 >26{//只有当前数字独立于前面数字一种情况，那dp[i] == dp[i - 1]dp[i] = dp[i - 1];}}//最后返回翻译方法的总和即可return dp.back();}
};