扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C++实现LeetCode(91.解码方法)
  • 639

0
分享到

C++实现LeetCode(91.解码方法)

2024-04-02 19:04:59 639人浏览 薄情痞子
摘要

[LeetCode] 91. Decode Ways 解码方法 A message containing letters from A-Z is being en

[LeetCode] 91. Decode Ways 解码方法

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

这道题要求解码方法，跟之前那道 Climbing Stairs 非常的相似，但是还有一些其他的限制条件，比如说一位数时不能为0，两位数不能大于 26，其十位上的数也不能为0，除去这些限制条件，跟爬梯子基本没啥区别，也勉强算特殊的斐波那契数列，当然需要用动态规划 Dynamci Programming 来解。建立一维 dp 数组，其中 dp[i] 表示s中前i个字符组成的子串的解码方法的个数，长度比输入数组长多多1，并将 dp[0] 初始化为1。现在来找状态转移方程，dp[i] 的值跟之前的状态有着千丝万缕的联系，就拿题目中的例子2来分析吧，当 i=1 时，对应s中的字符是 s[0]='2'，只有一种拆分方法，就是2，注意 s[0] 一定不能为0，这样的话无法拆分。当 i=2 时，对应s中的字符是 s[1]='2'，由于 s[1] 不为0，那么其可以被单独拆分出来，就可以在之前 dp[i-1] 的每种情况下都加上一个单独的2，这样 dp[i] 至少可以有跟 dp[i-1] 一样多的拆分情况，接下来还要看其能否跟前一个数字拼起来，若拼起来的两位数小于等于26，并且大于等于 10（因为两位数的高位不能是0），那么就可以在之前 dp[i-2] 的每种情况下都加上这个二位数，所以最终 dp[i] = dp[i-1] + dp[i-2]，是不是发现跟斐波那契数列的性质吻合了。所以0是个很特殊的存在，若当前位置是0，则一定无法单独拆分出来，即不能加上 dp[i-1]，就只能看否跟前一个数字组成大于等于 10 且小于等于 26 的数，能的话可以加上 dp[i-2]，否则就只能保持为0了。具体的操作步骤是，在遍历的过程中，对每个数字首先判断其是否为0，若是则将 dp[i] 赋为0，若不是，赋上 dp[i-1] 的值，然后看数组前一位是否存在，如果存在且满足前一位是1，或者和当前位一起组成的两位数不大于 26，则当前 dp[i] 值加上 dp[i - 2]。最终返回 dp 数组的最后一个值即可，代码如下：

c++ 解法一：


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

Java 解法一：


class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for (int i = 1; i < dp.length; ++i) {
            dp[i] = (s.charAt(i - 1) == '0') ? 0 : dp[i - 1];
            if (i > 1 && (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6'))) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[s.length()];
    }
}

下面这种方法跟上面的方法的思路一样，只是写法略有不同：

C++ 解法二：


class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        vector<int> dp(s.size() + 1, 0);
        dp[0] = 1;
        for (int i = 1; i < dp.size(); ++i) {
            if (s[i - 1] != '0') dp[i] += dp[i - 1];
            if (i >= 2 && s.substr(i - 2, 2) <= "26" && s.substr(i - 2, 2) >= "10") {
                dp[i] += dp[i - 2];
            }
        }
        return dp.back();
    }
};

Java  解法二：


class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for (int i = 1; i < dp.length; ++i) {
            if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1];
            if (i >= 2 && (s.substring(i - 2, i).compareTo("10") >= 0 && s.substring(i - 2, i).compareTo("26") <= 0)) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[s.length()];
    }
}

我们再来看一种空间复杂度为 O(1) 的解法，用两个变量 a, b 来分别表示 s[i-1] 和 s[i-2] 的解码方法，然后从 i=1 开始遍历，也就是字符串的第二个字符，判断如果当前字符为 '0'，说明当前字符不能单独拆分出来，只能和前一个字符一起，先将 a 赋为0，然后看前面的字符，如果前面的字符是1或者2时，就可以更新 a = a + b，然后 b = a - b，其实 b 赋值为之前的 a，如果不满足这些条件的话，那么 b = a，参见代码如下：

C++ 解法三：


class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        int a = 1, b = 1, n = s.size();
        for (int i = 1; i < n; ++i) {
            if (s[i] == '0') a = 0;
            if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6')) {
                a = a + b;
                b = a - b;
            } else {
                b = a;
            }
        }
        return a;
    }
};

Java 解法三：


class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;
        int a = 1, b = 1, n = s.length();
        for (int i = 1; i < n; ++i) {
            if (s.charAt(i) == '0') a = 0;
            if (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) <= '6')) {
                a = a + b;
                b = a - b;
            } else {
                b = a;
            }
        }
        return a;
    }
}

到此这篇关于C++实现LeetCode(91.解码方法)的文章就介绍到这了,更多相关C++实现解码方法内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

--结束END--

本文标题: C++实现LeetCode(91.解码方法)

本文链接: https://lsjlt.com/news/130753.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

猜你喜欢
  • C++实现LeetCode(91.解码方法)
    [LeetCode] 91. Decode Ways 解码方法 A message containing letters from A-Z is being en...
    99+
    2024-04-02
  • C++实现LeetCode(89.格雷码)
    [LeetCode] 89.Gray Code 格雷码 The gray code is a binary numeral system where two success...
    99+
    2024-04-02
  • C++实现LeetCode翻转整数的方法
    这篇文章主要介绍“C++实现LeetCode翻转整数的方法”，在日常操作中，相信很多人在C++实现LeetCode翻转整数的方法问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C++实现LeetCode翻转整数...
    99+
    2023-06-20
  • C++ffmpeg硬件解码的实现方法
    目录什么是硬件解码为什么要使用硬件解码怎样使用硬件解码注意事项关键函数解析什么是硬件解码 普通解码是利用cpu去解码也就是软件解码 硬件解码就是利用gpu去解码 为什么要使用硬件解码...
    99+
    2024-04-02
  • Java实现LeetCode的方法
    小编给大家分享一下Java实现LeetCode的方法，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可...
    99+
    2023-06-20
  • C++实现LeetCode( 69.求平方根)
    [LeetCode] 69. Sqrt(x) 求平方根 Implement int sqrt(int x). Compute and return the square r...
    99+
    2024-04-02
  • C++实现LeetCode(37.求解数独)
    [LeetCode] 37. Sudoku Solver 求解数独 Write a program to solve a Sudoku puzzle by filling the e...
    99+
    2024-04-02
  • C++实现LeetCode字型转换字符串的方法
    这篇文章主要介绍“C++实现LeetCode字型转换字符串的方法”，在日常操作中，相信很多人在C++实现LeetCode字型转换字符串的方法问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C++实现LeetCo...
    99+
    2023-06-20
  • C++实现LeetCode(38.计数和读法)
    [LeetCode] 38. Count and Say 计数和读法 The count-and-say sequence is the sequence of integers w...
    99+
    2024-04-02
  • C++怎么实现LeetCode
    这篇文章主要介绍“C++怎么实现LeetCode”，在日常操作中，相信很多人在C++怎么实现LeetCode问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C++怎么实现LeetCode”的疑惑有所帮助！接下来...
    99+
    2023-06-20
  • C++如何实现LeetCode
    这篇文章给大家分享的是有关C++如何实现LeetCode的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。[LeetCode] Reverse Linked List 倒置链表Reverse a singly lin...
    99+
    2023-06-20
  • C++实现LeetCode(50.求x的n次方)
    [LeetCode] 50. Pow(x, n) 求x的n次方 Implement pow(x, n), which calculates x ...
    99+
    2024-04-02
  • C++中如何实现LeetCode
    这篇文章主要为大家展示了“C++中如何实现LeetCode”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“C++中如何实现LeetCode”这篇文章吧。[LeetCode] 35. Search ...
    99+
    2023-06-20
  • C++中怎么实现LeetCode
    今天就跟大家聊聊有关C++中怎么实现LeetCode，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。[LeetCode] 126. Word Ladder II 词语阶梯之二Given...
    99+
    2023-06-20
  • C++详解实现Stack方法
    目录栈简介stack模拟示例代码开发环境运行结果栈简介 栈本着先进后出的原则，来存取数据。作为数据结构中的一种，这里不多介绍相关栈。仅以此文记录C++中栈的实现，可帮助提升编程能力与...
    99+
    2024-04-02
  • C++实现LeetCode(28.实现strStr()函数)
    [LeetCode] 28. Implement strStr() 实现strStr()函数 Implement strStr(). Return the index of...
    99+
    2024-04-02
  • C/C++ Crypto密码库调用的实现方法
    目录Sha256加密算法AES 加密与解密AES2 加密:Base64加解密:Hash加密算法RSA加密算法Crypt库实现RSA加密Crypto 库是C/C++的加密算法库，这个加...
    99+
    2024-04-02
  • C++实现LeetCode(17.电话号码的字母组合)
    [LeetCode] 17. Letter Combinations of a Phone Number 电话号码的字母组合 Given a string containing di...
    99+
    2024-04-02
  • C++实现LeetCode(120.三角形)
    [LeetCode] 120.Triangle 三角形 Given a triangle, find the minimum path sum from top to bottom....
    99+
    2024-04-02
  • C++实现LeetCode(46.全排列)
    [LeetCode] 46. Permutations 全排列 Given a collection of distinct integers, return a...
    99+
    2024-04-02
软考高级职称资格查询
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作