题解 | #把数字翻译成字符串#

把数字翻译成字符串

https://www.nowcoder.com/practice/046a55e6cd274cffb88fc32dba695668

方法:动态规划

1、遍历字符串,使用一个数组dp存储字符串不同位置结尾的译码结果次数,可以得到如下的状态转移方程

如果当前字符可以和前面一个字符组成一个译码结果:dp[i] = dp[i - 1] + dp[i - 2]

否则,dp[i] = dp[i - 1]

2、数组最后一个元素就为字符串的译码结果次数。

注意,当字符串中出现‘0’时,需要进行特殊处理

时间复杂度:o(n)

空间复杂度:o(n)

class Solution {
  public:
    int solve(string nums) {
        // 特殊情况处理
        if (nums[0] == '0')
            return 0;
        for (int i = 1; i < nums.length(); i++)
            if (nums[i] == '0' && nums[i - 1] != '1' && nums[i - 1] != '2')
                return 0;

        vector<int> dp(nums.length() + 1, 1);
        for (int i = 2; i <= nums.length(); i++) {
            //在11-19,21-26之间的情况
            if ((nums[i - 2] == '1' && nums[i - 1] != '0') || (nums[i - 2] == '2' &&
                    nums[i - 1] > '0' && nums[i - 1] < '7'))
                dp[i] = dp[i - 1] + dp[i - 2];
            else
                dp[i] = dp[i - 1];
        }
        return dp[nums.length()];
    }
};

刷题题解(c++) 文章被收录于专栏

算法题题解(c++)

全部评论

相关推荐

07-07 11:33
江南大学 Java
已经在暑假实习了&nbsp;,没有明确说有hc,纠结实习到八月份会不会有点影响秋招毕竟感觉今年好多提前批
程序员小白条:92的话准备提前批,其他没必要,没面试机会的,而且你要准备充分,尤其八股和算法题
点赞 评论 收藏
分享
程序员小白条:你是沟通了900个,不是投了900份简历,你能投900份,意味着对面都要回复你900次,你早就找到实习了,没亮点就是这样的,别局限地区,时间投的也要早,现在都要7月了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 12:10
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务