☆打卡算法☆LeetCode 91、解码方法 算法解析

举报
恬静的小魔龙 发表于 2022/03/02 09:13:09 2022/03/02
【摘要】 推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。 一、题目 1、算法题目“给定一个只含数字的字符串,计算并返回解码方法的总和。”题目链接:来源:力扣(LeetCode)链接:91. 解码方法 - 力扣(...

推荐阅读

大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个只含数字的字符串,计算并返回解码方法的总和。”

题目链接:

来源:力扣(LeetCode)

链接:91. 解码方法 - 力扣(LeetCode) (leetcode-cn.com)

2、题目描述

一条包含字母 A-Z 的消息通过以下映射进行了 编码 :

‘A’ -> “1”
‘B’ -> “2”

‘Z’ -> “26”

要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,“11106” 可以映射为:

  • “AAJF” ,将消息分组为 (1 1 10 6)
  • “KJF” ,将消息分组为 (11 10 6)
    注意,消息不能分组为  (1 11 06) ,因为 “06” 不能映射为 “F” ,这是由于 “6” 和 “06” 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1:
输入: s = "12"
输出: 2
解释: 它可以解码为 "AB"1 2)或者 "L"12)。
示例 2:
输入: s = "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6)

二、解题

1、思路分析

这道题动态规划、递归都可以。

首先分析题意,对于给定的字符串s,对它进行解码,返回解码数量。

具体来说就是,对于字符串s,在解码的时候判断使用了s中的那些字符,会出现两种情况:

  • 使用了一个字符,对s[i]进行解码,可以解码成A~I中的某个字母,再根绝剩余字符进行解码
  • 使用了两个字符,既s[i]和s[i-1]进行解码,与第一种情况类似,s[i-1]不能等于0,并且s[i-1]和s[i]组成的整数必须小于等于26

由此,可以写出状态转移方式,进行动态规划:

fi=fi−1,其中 s[i]/0
fi=fi−2,其中 s[i−1]≠0 ,并且 10*s[i−1]+s[i]≤26

2、代码实现

代码参考:

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        // a = f[i-2], b = f[i-1], c=f[i]
        int a = 0, b = 1, c = 0;
        for (int i = 1; i <= n; ++i) {
            c = 0;
            if (s.charAt(i - 1) != '0') {
                c += b;
            }
            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
                c += a;
            }
            a = b;
            b = c;
        }
        return c;
    }
}

image.png

3、时间复杂度

时间复杂度 : O(n)

其中n是字符串s的长度。

空间复杂度: O(n)

如果使用数组进行状态转移,空间复杂度为O(n),如果仅使用三个变量,空间复杂度为O(1)。

三、总结

这道题首先要理解清楚解码规则。

找出动态规划方程,使用动态规划找出答案。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200