Go Java算法之解码方法_F11 - 专业站长和开发者的学习网站

分享到

Go Java算法之解码方法

java 来源：互联网作者：佚名发布时间：2022-08-20 20:53:12 人浏览

摘要

解码方法一条包含字母 A-Z 的消息通过以下映射进行了编码： A - 1 B - 2 ... Z - 26 要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如

解码方法

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

示例 3：

输入：s = "0"

输出：0

解释：没有字符映射到以 0 开头的数字。

含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。

由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。

提示：

1 <= s.length <= 100

s 只包含数字，并且可能包含前导零。

方法一：动态规划（Java）

对于给定的字符串 s ，设它的长度为 n ，其中的字符从左到右依次为 s[1],s[2],...,s[n]。我们可以使用动态规划的方法计算出字符串的解码方法数。

具体地，设 fi表示字符串s的前i个字符 s[1..i]的解码方法数。在进行状态转移时，我们可以考虑最后一次解码使用了 s中的哪些字符

class Solution {

public int numDecodings(String s) {

int n = s.length();

int[] f = new int[n + 1];

f[0] = 1;

for (int i = 1; i <= n; ++i) {

if (s.charAt(i - 1) != '0') {

f[i] += f[i - 1];

}

if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {

f[i] += f[i - 2];

}

return f[n];

}

时间复杂度：o（n）

空间复杂度：o（n）

方法二：动态规划——优化（go）

具体的方法思路请看上文表述，本方法对空间复杂度进行了优化，通过使用临时变量的方式，使得空间复杂度从o(n)降为o(1)

func numDecodings(s string) int {

n := len(s)

// a = f[i-2], b = f[i-1], c = f[i]

a, b, c := 0, 1, 0

for i := 1; i <= n; i++ {

c = 0

if s[i-1] != '0' {

c += b

}

if i > 1 && s[i-2] != '0' && ((s[i-2]-'0')*10+(s[i-1]-'0') <= 26) {

c += a

}

a, b = b, c

}

return c

}

时间复杂度：o（n）

空间复杂度：o（1）

您可能感兴趣的文章 :

原文链接 : https://juejin.cn/post/7128770715419377671

Tag : Go(37)

SpringBoot自定义错误处理逻辑介绍

1. 自定义错误页面将自定义错误页面放在 templates 的 error 文件夹下，SpringBoot 精确匹配错误信息，使用 4xx.html 或者 5xx.html 页面可以打印错误
Java实现手写一个线程池的代码

线程池技术想必大家都不陌生把，相信在平时的工作中没有少用，而且这也是面试频率非常高的一个知识点，那么大家知道它的实现原理和
Java实现断点续传功能的代码

题目实现：网络资源的断点续传功能。二、解题思路获取要下载的资源网址显示网络资源的大小上次读取到的字节位置以及未读取的字节
你可知HashMap为什么是线程不安全的

HashMap 的线程不安全 HashMap 的线程不安全主要体现在下面两个方面在 jdk 1.7 中，当并发执行扩容操作时会造成环形链和数据丢失的情况在
ArrayList的动态扩容机制的介绍

对于 ArrayList 的动态扩容机制想必大家都听说过，之前的文章中也谈到过，不过由于时间久远，早已忘却。所以利用这篇文章做做笔记，加
JVM基础之字节码的增强技术介绍

字节码增强技术在上文中，着重介绍了字节码的结构，这为我们了解字节码增强技术的实现打下了基础。字节码增强技术就是一类对现有字
Java中的字节码增强技术

1.字节码增强技术字节码增强技术就是一类对现有字节码进行修改或者动态生成全新字节码文件的技术。参考地址 2.常见技术技术分类类
Redis BloomFilter布隆过滤器原理与实现

Bloom Filter 概念布隆过滤器（英语：Bloom Filter）是1970年由一个叫布隆的小伙子提出的。它实际上是一个很长的二进制向量和一系列随机映射
Java C++算法题解leetcode801使序列递增的最小交换次

题目要求思路：状态机DP 实现一：状态机 Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int minSwap(int[] nums1, int[] nums2) { int n
Mybatis结果集映射与生命周期介绍

一、ResultMap结果集映射 1、设计思想对简单的语句做到零配置，对于复杂一点的语句，只需要描述语句之间的关系就行了 2、resultMap的应用场