力扣LeetCode经典算法 把数字翻译成字符串

数据结构（五十八）

学习数据结构与算法过程中的心得体会以及知识点的整理，方便我自己查找，也希望可以和大家一起交流。

—— 把数字翻译成字符串 ——

1.题目描述

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 :

输入:
12258
输出:
5
解释:
12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”

2.代码

c

int translateNum(int num){int* nums = (int *) malloc (sizeof(int) * 20);int* ans = (int *) malloc (sizeof(int) * 20);int numsSize = 0;while (num > 9){//将数字的各个位分别储存nums[numsSize] = num % 10;numsSize++;num = (num - num % 10) / 10;}nums[numsSize] = num;numsSize++;for(int left = 0, right = numsSize - 1; left < right; left++, right--) {int tmp = nums[left]; nums[left] = nums[right]; nums[right] = tmp;}ans[0] = 1;if(nums[0] * 10 + nums[1] < 26 && nums[0] * 10 + nums[1] > 9)ans[1] = ans[0] + 1;elseans[1] = ans[0];for(int i = 2; i < numsSize; i++){if(nums[i - 1] * 10 + nums[i] < 26 && nums[i - 1] * 10 + nums[i] > 9)ans[i] = ans[i - 2] + ans[i - 1];elseans[i] = ans[i - 1];}return ans[numsSize - 1];
}

其中如果嫌麻烦，可以直接用正则表达式。代码如下：

int translateNum(int num){int* nums = (int *) malloc (sizeof(int) * 20);int* ans = (int *) malloc (sizeof(int) * 20);int numsSize = 0;while (num > 9){//将数字的各个位分别储存nums[numsSize] = num % 10;numsSize++;num = (num - num % 10) / 10;}nums[numsSize] = num;numsSize++;for(int left = 0, right = numsSize - 1; left < right; left++, right--) {int tmp = nums[left]; nums[left] = nums[right]; nums[right] = tmp;}ans[0] = 1;ans[1] = (nums[0] * 10 + nums[1] < 26 && nums[0] * 10 + nums[1] > 9) ? ans[0] + 1 : ans[0];for(int i = 2; i < numsSize; i++)ans[i] = (nums[i - 1] * 10 + nums[i] < 26 && nums[i - 1] * 10 + nums[i] > 9) ? ans[i - 2] + ans[i - 1] : ans[i - 1];return ans[numsSize - 1];
}

这道题其实比较难，具体的思路如下：
如果邻近nums[i - 1]和 nums[i] 组成的数字（前者为十位，后者为个位）num_tmp如果在[10, 25]（闭区间）之间，我们就可以从ans[i - 2] 直接一步跳到dp[i], 再加上任何情况都存在的ans[i - 1]跳到dp[i]，那么就为ans[i] = (nums[i - 1] * 10 + nums[i] < 26 && nums[i - 1] * 10 + nums[i] > 9) ? ans[i - 2] + ans[i - 1] : ans[i - 1];，于是我们得到了迭代公式。接着对初始点进行处理，ans[0] = 1是毋庸置疑的，ans[1] 的处理类似上面提到的处理，如果nums[0]和nums[1]组成的数字在[10, 25]之间，那么就说明ans[1] = ans[0] + 1，因为此时可以从索引-1处一步跳达，也可以从索引0处一步跳达，1 + 1 = 2；否则，ans[1] = ans[0]。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！