题目

题解

这道题和91题很像，区别在于这道题从0开始编码，就不用讨论当前数为0的情况，因此更简单，可以转化为字符串使用91题的方法进行解决，这里不再赘述，也可以使用循环求余法，从右往左计算，具体见注释

  • 时间复杂度$O(n)$
  • 空间复杂度$O(1)$
//和91类似，区别是这个编码从0开始，91从1开始
//而且91是字符串，这道题也可以转化为字符串用91中的方法
//这里用取余法，注意这里是从右往左，因为是从0开始，从左往右从右往左都可以
class Solution {
public:
    int translateNum(int num) {
        int pre=1, cur=1, x, y=num%10;//pre是dp[i-1]，cur是dp[i]，x是当前位，y是上一位
        while(num){//num还没除尽就继续遍历
            num /= 10;
            x = num%10;//这两部是更新x
            int tmp = cur;//这时tmp变为dp[i-1]，cur是dp[i]，pre是dp[i-2]
            int xy = x*10 + y;//将x，y合并看其大小
            if(xy<=25 && xy>=10) cur = tmp + pre;//若可以合并，则dp[i]=dp[i-1]+dp[i-2]
            else cur = tmp;//否则dp[i] = dp[i-1]
            pre = tmp;//更新pre
            y = x;//更新y（x在循环体开头更新）
        }
        return cur;
    }
};