题解 | #把数字翻译成字符串#
把数字翻译成字符串
https://www.nowcoder.com/practice/046a55e6cd274cffb88fc32dba695668
class Solution {
public:
int solve(string nums) {
if(nums[0]=='0') return 0;
int n=nums.size();
vector<int> dp(n+1,1);
for(int i=2;i<=n;i++){
if(nums[i-1]=='0'){
if(nums[i-2]>'2') return 0;//0的前面不是1、2时为非法串
dp[i]=dp[i-2];//与前面的1、2绑定
}
else if(nums[i-2]=='1' || (nums[i-2]=='2' && nums[i-1]<='6'))
dp[i]=dp[i-1]+dp[i-2];
else
dp[i]=dp[i-1];
}
return dp[n];
}
};
在dp数组中只用到了连续2个值，空间优化：
class Solution {
public:
int solve(string nums) {
if(nums[0]=='0') return 0;
int n=nums.size();
int d1=1,d2=1,d3=1;
for(int i=2;i<=n;i++){
if(nums[i-1]=='0'){
if(nums[i-2]>'2') return 0;//0的前面不是1、2时为非法串
d3=d1;//与前面的1、2绑定
}
else if(nums[i-2]=='1' || (nums[i-2]=='2' && nums[i-1]<='6'))
d3=d1+d2;
else
d3=d2;
d1=d2;d2=d3;
}
return d3;
}
};
时间复杂度O(n)，空间复杂度O(1)
