陈中正的网络日志

Leetcode: Decode Ways

题目

https://oj.leetcode.com/problems/decode-ways/

分析

  1. Leetcode: Climbing Stairs这道题类似, 都是用类似斐波那契数列的算法解决问题。只不过在递归或者迭代时加一点条件判断。

  2. 运用动态规划思想, 先想出递归的算法, 然后再改变成迭代的方式提高算法效率。

  3.  递归的算法:

      设前n个数的decode ways是f(n), 则

            若最后俩数小于26, 则

                  f(n) = f(n-1) + f(n-2);

            否则

                  f(n) = f(n-1);

  1. 再改造成迭代的算法:

      设前n个数的decode ways是s(n), 则

            若最后俩数小于26, 则

                  s(n) = s(n-1) + s(n-2);

            否则

                  s(n) = s(n-1);

  1. 因为“0”是一个比较特殊的数字, 所以针对一些测试用例, 需要对算法进行一些改进。 

这些改进如果没有测试用例, 感觉很难就作出来。 这大概也是测试工程师的作用吧。

代码

class Solution
{
public:
    int numDecodings(string s)
    {
        if (s.empty())
            return 0;
        if (s[0] == '0')
            return 0;
        if (s.size() == 1)
            return 1;

        int a, b, c;
        a = 1;
        b = 1; 
        for (int i = 1; i < s.size(); i++)
        {
            if (s[i] == '0' && s[i-1] == '0')
                return 0;
            if (s[i] == '0' && s[i-1] > '2')
                return 0;

            if (stoi(s.substr(i-1, 2)) > 26)
                c = b;
            else if (s[i] == '0')
                c = a;
            else if (s[i-1] == '0')
                c = b;
            else
                c = a + b;

            a = b;
            b = c;
        }

        return c;
    }
};

参考

http://blog.csdn.net/worldwindjp/article/details/19938131

http://fisherlei.blogspot.com/2013/01/leetcode-decode-ways-solution.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/38902215

Categories:  OJ题解 

« Leetcode: Binary Tree Level Order Traversal Leetcode: Word Ladder »