美文网首页
91.解码方法

91.解码方法

作者: HITZGD | 来源:发表于2018-11-22 20:32 被阅读0次

    题目
    一条包含字母 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) 。

    思路
    可以看作一个动态规划的问题,

    首先,如果第一位上是0,那么无法转码,返回0;

    其次,每次转码,都可以看看第i位跟第i-1位的数字是否小于等于26,如果符合的话,我们在i-2位上解码;如果第i位不等于0的话,说明我们相当于在第i-1位上解码。如果两个都符合,相当于:dp[i] = dp[i-1] + dp[i-2];

    #include <string>
    #include <vector>
    using namespace std;
    class Solution {
    public:
        int numDecodings(string s) {
            if (s.size() == 0 || s.at(0) == '0') return 0;
            vector<int> nums(s.size(), 0);
            nums[0] = s[0] == '0' ? 0 : 1;
            if (s.size() == 1)
            {
                return nums[0];
            }
            int k = (s.at(0) > '0' && s.at(1) > '0') ? 1 : 0;
            nums[1] = k + ((s.at(0) == '1' || s.at(0) == '2' && s.at(1) <= '6') ? 1 : 0);
            for (int i = 2; i < s.size(); i++)
            {
                if (s.at(i) != '0')
                {
                    nums[i] += nums[i - 1];
                }
                if (s.at(i - 1) == '1' || s.at(i - 1) == '2' && s.at(i) <= '6')
                {
                    nums[i] += nums[i - 2];
                }
            }
            return nums[s.size() - 1];
        }
    };
    
    int main(int argc, char* argv[])
    {
        string test = "1";
        auto res = Solution().numDecodings(test);
        return 0;
    }
    
    
    
    原文:https://blog.csdn.net/u012156116/article/details/79763005 
    

    相关文章

      网友评论

          本文标题:91.解码方法

          本文链接:https://www.haomeiwen.com/subject/operqqtx.html