如何快速来一套苹果全家桶( 二 ) _数字

分析完毕后用下图来验证一下吧。

文章插图
怎么样，分析的正确吗？
接下来让我们数一数每一个位置所有可能的解释个数：
右数第一个数字是1个
右数第二个数字是2个
右数第三个数字是3个
右数第四个数字是5个
这就是我们在本文开头提到的那个数列，也就是著名的斐波那契数列，现在你应该明白了吧。
公式提炼

文章插图
为什么该问题会形成斐波那契数列数列呢？
注意，接下来是重点。
我们记以右数第i个数字为开头的字符串所能形成的编码种类个数为F(i) ，那么如果我们单独将第i个数字单独解释，那么能形成的编码种类个数就取决于F(i-1) 。
而如果我们将第i和和第i-1这两个数字单独解释，那么能形成的编码种类个数就取决于F(i-2) ，当然，这里有个前提，那就是第i和和第i-1这两个数字形成的整数必须在10~26之间，这样我们才能将其解释称为一个大写字母，否则F(i)的值就只取决于F(i-1) ，即：
F(i) = F(i-1) + F(i-2) if 10 <= substr(i,i+1) <= 26F(i) = F(i-1)else
现在你该知道了吧，原来这里确实存在一个稍微有点变型的斐波那契数列。
有了这些分析，还怕写不出代码吗？
代码实现
以下仅仅将上述公式翻译成代码。

int numDecodings(string s) {int len = s.length();if (len == 0||s=="0")return 0;vectorF(len+1, 1);for (int i = len - 1; i >= 0; i--){if (s[i] == '0' )F[i] = 0;else if (i == len - 1)F[i] = 1;else if (atoi(s.substr(i, 2).c_str()) <= 26)F[i] = F[i + 1] + F[i + 2];elseF[i] = F[i + 1];}return F[0];}

总结
有时你会发现算法其实还是挺有趣的(前提是你能想出解决方法:) ) ，在这个题目中经过我们的分析后发现，这其实就是初中学过的斐波那契数列而已。可能我们一下不能想到其本质，但是我们从最简单的情况下开始着手分析并找出规律，最后通过规律提炼出公式才发现这其实是斐波那契数列的变型，用代码实现一个斐波那契数列是非常简单的，真正的价值在于这背后的分析过程，希望对你能有所启发。
为你推荐
图解：LRU Cache
图解：最长匹配括号
图解：二叉树最低公共祖先

文章插图
码农的荒岛求生
微信号 : -it