NC116把数字翻译成字符串
NC116把数字翻译成字符串
- 1、题目描述：
-3、 设计思想：
详细操作流程看下图：
-5、代码：
c++版本:
class Solution {
public:
/**
* 解码
* @param nums string字符串 数字串
* @return int整型
*/
int solve(string nums) {
// write code here
if (nums[0] == '0') return 0;
vector<int>dp(nums.size() + 10,0);//dp[i]的含义代表长度在i位置时有几种翻译办法
dp[0] = 1;//在第0个字符的时候只有一个字母所以只有一种翻译办法
for(int i = 1;i < nums.size();i ++){
if(nums[i] == '0'){
if(nums[i-1] == '1' || nums[i-1] == '2')
{
if(i == 1) dp[i] = 1;//特判字符串长度为2
else dp[i] = dp[i-2];//因为 10 20 这样的只有一种对应方案，所以此时dp[i]取决于dp[i-2]
}
}
else if(nums[i - 1] == '1' || (nums[i - 1] == '2' && nums[i] >= '1' && nums[i] <= '6')){
/*11-26 抛去 20这样的组合
但是当i==1的时候如 12 21 这样有两种方案
当i>1时候dp[i] 取决于 dp[i-1] 和 dp[i-2]的和
*/
if(i == 1) dp[i] = 2;
else dp[i] = dp[i-1] + dp[i-2];
}else{
//>=27这样的组合
dp[i] = dp[i-1];
}
}
return dp[nums.size()-1];
}
};
Java版本：
import java.util.*;
public class Solution {
/**
*
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
C++岗位面试真题宝典 文章被收录于专栏
整篇专刊共分为6章，涵盖C++基础、C++操作系统、C++计算机网络、C++数据库、C++设计模式与算法面试真题。 购买须知 1、专刊报名后，在个人主页-学习-已购-专刊即可快速进入学习。2、专刊为虚拟商品，交付形式为图文，一经购买，即可解锁内容，所以概不退款。 3、专刊版权归本牛客所有，任何机构、媒体、网站或个人未经本网协议授权不得转载、链接、转贴或以其他方式复制发布/发表，违者将依法追究责任。
查看8道真题和解析