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

把数字翻译成字符串

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++)

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 12:10
点赞 评论 收藏
分享
06-12 10:50
门头沟学院 Java
你的不定积分没加C:我怎么在学院群看到了同样的话
点赞 评论 收藏
分享
白火同学:只是实习的话,你这份简历应该也差不多了。真要优化的话,因为面实习的话,没有开发经验,面试更重视技术栈水平。 1、重视JavaSE的基础吧,集合、泛型算是比较基础的基础,多线程、反射、JVM内存模型才是基础; 2、技术栈写到具体的点,比如Elasticsearch的使用写到某个点,限制面试官自由发挥,防止问了相关问题最后又答不上,如果真没把握建议不写,降低面试官的心理预期; 3、技术栈不要重复,比如技术栈第二条和第八条可以合并改为“熟悉Redis中间件,包括基本数据结构、缓存策略、持久化机制,了解缓存三剑客及其解决方案,并有相关项目经验。”; 4、项目指标量化,比如“达到xx秒的响应速度”(不过这个就有点偏校招社招的要求了,实习简历不写也无伤大雅)。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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