每日一题：解码方法

题目91：解码方法一条包含字母 A-Z 的消息通过以下方式进行了编码：'A' -> 1'B' -> 2...'Z' -> 26给定一个只包含数字的非空字符串，请

题目91：解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1'B' -> 2...'Z' -> 26给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例1：

输入: "12"输出: 2解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。示例2：

输入: "226"输出: 3解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。分析

dp问题，用dp[i]表示str[0-i]的解码方法总数，则有

1. 若s[i]等于'0'，如果s[i-1]等于'1'或者'2'，则dp[i]=dp[i-2]，否则return 0。

2. 若s[i-1]s[i]两个字符可以转换为整数为1-26，则dp[i]=dp[i-1]+dp[i-2]，如果不可以转换，则dp[i]=dp[i-1]。

代码

class Solution {public: int numDecodings(string s) { if (s.empty()) return 0; if (s[0] == '0') return 0; vector dp(s.size()); dp[0] = 1; for (int i = 1; i = 0) ? dp[i-2] : 1; } else { return 0; } } else { if (s[i-1] == '1' || (s[i-1] == '2' dp[i] = dp[i-1] + tem; } else { dp[i] = dp[i-1]; } } } return dp[s.size()-1]; }};

一文让你搞懂设计模式

RAII妙用之ScopeExit

深入浅出虚拟内存

深入浅出虚拟内存（二）绘制虚拟内存排布图

深入浅出虚拟内存（三）堆内存分配及malloc实现原理

RAII妙用之计算函数耗时

一文吃透C++11中auto和decltype知识点

【来源：国外高防服务器 http://www.558idc.com/stgf.html 欢迎留下您的宝贵建议】