【动态规划】【C++算法】639 解码方法 II

作者推荐

【矩阵快速幂】封装类及测试用例及样例

涉及知识点

动态规划 字符串 滚动向量

LeetCode 639. 解码方法 II

一条包含字母 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” 不同。
除了 上面描述的数字字母映射方案，编码消息中可能包含 '’ 字符，可以表示从 ‘1’ 到 ‘9’ 的任一数字（不包括 ‘0’）。例如，编码字符串 "1" 可以表示 “11”、“12”、“13”、“14”、“15”、“16”、“17”、“18” 或 “19” 中的任意一条消息。对 “1*” 进行解码，相当于解码该字符串可以表示的任何编码消息。
给你一个字符串 s ，由数字和 '’ 字符组成，返回 解码 该字符串的方法 数目 。
由于答案数目可能非常大，返回 109 + 7 的 模 。
示例 1：
输入：s = ""
输出：9
解释：这一条编码消息可以表示 “1”、“2”、“3”、“4”、“5”、“6”、“7”、“8” 或 “9” 中的任意一条。
可以分别解码成字符串 “A”、“B”、“C”、“D”、“E”、“F”、“G”、“H” 和 “I” 。
因此，“" 总共有 9 种解码方法。
示例 2：
输入：s = "1”
输出：18
解释：这一条编码消息可以表示 “11”、“12”、“13”、“14”、“15”、“16”、“17”、“18” 或 “19” 中的任意一条。
每种消息都可以由 2 种方法解码（例如，“11” 可以解码成 “AA” 或 “K”）。
因此，“1*” 共有 9 * 2 = 18 种解码方法。
示例 3：
输入：s = “2*”
输出：15
解释：这一条编码消息可以表示 “21”、“22”、“23”、“24”、“25”、“26”、“27”、“28” 或 “29” 中的任意一条。
“21”、“22”、“23”、“24”、“25” 和 “26” 由 2 种解码方法，但 “27”、“28” 和 “29” 仅有 1 种解码方法。
因此，“2*” 共有 (6 * 2) + (3 * 1) = 12 + 3 = 15 种解码方法。
提示：
1 <= s.length <= 105
s[i] 是 0 - 9 中的一位数字或字符 ‘*’

分析

时间复杂度：O(nm) n=s.length m = 9（1到9)。

动态规划的细节，方便检查

动态规划的状态表示dp[j]表示s[0,i) 以 j+'A’结尾的合法串数量。dp[0]是占位符，无意义，请忽略
动态规划的转移方程见下文
动态规划的初始状态如果是*,dp[1,9]=1，否则dp[s[0]-‘A’]=1
动态规划的填表顺序i从1到大,确保动态规划的无后效性
动态规划的返回值求和 [ 1 , 26 ] j ^{j}_{[1,26]} [1,26]j​dp[j]

动态规划的转移方程

有两种转移方式：
新建字符： 当前字符必须是[1,9],前一个字符不限。
和前面的串最后一个字符结合：
当前字符：[0,9] 前一字符：1
或
当前字符：[0,6] 前一字符 2

代码

封装类

template<int MOD = 1000000007>
class C1097Int
{
public:
	C1097Int(long long llData = 0) :m_iData(llData% MOD)
	{

	}
	C1097Int  operator+(const C1097Int& o)const
	{
		return C1097Int(((long long)m_iData + o.m_iData) % MOD);
	}
	C1097Int& operator+=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData + o.m_iData) % MOD;
		return *this;
	}
	C1097Int& operator-=(const C1097Int& o)
	{
		m_iData = (m_iData + MOD - o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator-(const C1097Int& o)
	{
		return C1097Int((m_iData + MOD - o.m_iData) % MOD);
	}
	C1097Int  operator*(const C1097Int& o)const
	{
		return((long long)m_iData * o.m_iData) % MOD;
	}
	C1097Int& operator*=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData * o.m_iData) % MOD;
		return *this;
	}
	bool operator<(const C1097Int& o)const
	{
		return m_iData < o.m_iData;
	}
	C1097Int pow(long long n)const
	{
		C1097Int iRet = 1, iCur = *this;
		while (n)
		{
			if (n & 1)
			{
				iRet *= iCur;
			}
			iCur *= iCur;
			n >>= 1;
		}
		return iRet;
	}
	C1097Int PowNegative1()const
	{
		return pow(MOD - 2);
	}
	int ToInt()const
	{
		return m_iData;
	}
private:
	int m_iData = 0;;
};

核心代码

class Solution {
public:
	int numDecodings(string s) {
		vector<C1097Int<>> pre(27);
		if ('*' == s[0])
		{
			for (int i = 1; i <= 9; i++)
			{
				pre[i] += 1;
			}
		}
		else
		{
			pre[s[0] - '0'] += 1;
		}
		for (int i = 1; i < s.length(); i++)
		{
			vector<C1097Int<>> dp(27);
			const auto total = std::accumulate(pre.begin()+1, pre.end(), C1097Int<>());			
			auto Add = [&dp, &pre,&total](const char& ch)
			{
				if ((ch >= '1') && (ch <= '9'))
				{
					dp[ch - '0'] += total;//新字符
				}
				dp[ch - '0' + 10] += pre[1];
				if ((ch >= '0') && (ch <= '6'))
				{
					dp[ch - '0' + 20] += pre[2];
				}
			};
			if ('*' == s[i])
			{
				for (char ch = '1'; ch <= '9'; ch++)
				{
					Add(ch);
				}
			}
			else
			{
				Add(s[i]);
			}
			pre.swap(dp);
		}
		return std::accumulate(pre.begin() + 1, pre.end(), C1097Int<>()).ToInt();
	}
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}
}


int main()
{
	string s;
	{
		Solution sln;
		s = "0";
		auto res = sln.numDecodings(s);
		Assert(0, res);
	}
	{
		Solution sln;
		s = "*";
		auto res = sln.numDecodings(s);
		Assert(9, res);
	}
	{
		Solution sln;
		s = "1*";
		auto res = sln.numDecodings(s);
		Assert(18, res);
	}
	{
		Solution sln;
		s = "2*";
		auto res = sln.numDecodings(s);
		Assert(15, res);
	}

	{
		Solution sln;
		s = "*********";
		auto res = sln.numDecodings(s);
		Assert(291868912, res);
	}
	
	{
		Solution sln;
		s = "**3*******";
		auto res = sln.numDecodings(s);
		Assert(351940699, res);
	}

	{
		Solution sln;
		s = "*1*3***4**6**";
		auto res = sln.numDecodings(s);
		Assert(632929394, res);
	}

	{
		Solution sln;
		s = "*1*3***4**6*7*";
		auto res = sln.numDecodings(s);
		Assert(468371306, res);
	}
}

改进

修改了三处：
一，初始化简洁。
二，total 包括dp[0]。
三，i从0开始。
代码更简洁。

class Solution {
public:
	int numDecodings(string s) {
		vector<C1097Int<>> pre(27);
		pre[0] = 1;
		for (int i = 0; i < s.length(); i++)
		{
			vector<C1097Int<>> dp(27);
			const auto total = std::accumulate(pre.begin(), pre.end(), C1097Int<>());			
			auto Add = [&dp, &pre,&total](const char& ch)
			{
				if ((ch >= '1') && (ch <= '9'))
				{
					dp[ch - '0'] += total;//新字符
				}
				dp[ch - '0' + 10] += pre[1];
				if ((ch >= '0') && (ch <= '6'))
				{
					dp[ch - '0' + 20] += pre[2];
				}
			};
			if ('*' == s[i])
			{
				for (char ch = '1'; ch <= '9'; ch++)
				{
					Add(ch);
				}
			}
			else
			{
				Add(s[i]);
			}
			pre.swap(dp);
		}
		return std::accumulate(pre.begin() + 1, pre.end(), C1097Int<>()).ToInt();
	}
};

2023年第一版

 class CBigMath
 {
 public:
	 static void AddAssignment(int* dst, const int& iSrc)
	 {
		 *dst = (*dst + iSrc) % s_iMod;
	 }

	 static void AddAssignment(int* dst, const int& iSrc, const int& iSrc1)
	 {
		 *dst = (*dst + iSrc) % s_iMod;
		 *dst = (*dst + iSrc1) % s_iMod;
	 }

	 static void AddAssignment(int* dst, const int& iSrc, const int& iSrc1, const int& iSrc2)
	 {
		 *dst = (*dst + iSrc) % s_iMod;
		 *dst = (*dst + iSrc1) % s_iMod;
		 *dst = (*dst + iSrc2) % s_iMod;
	 }

	 static void SubAssignment(int* dst, const int& iSrc)
	 {
		 *dst = (s_iMod - iSrc + *dst) % s_iMod;
	 }
	 static int Add(const int& iAdd1, const int& iAdd2)
	 {
		 return (iAdd1 + iAdd2) % s_iMod;
	 }
	 static int Mul(const int& i1, const int& i2)
	 {
		 return((long long)i1 *i2) % s_iMod;
	 }
 private:
	 static const int s_iMod = 1000000007;
 };
 
  class Solution {
 public:
	 int numDecodings(string s) {
		 vector<int> preDp(27);
		 if ('*' == s[0])
		 {
			 for (int i = 1; i < 10; i++)
			 {
				 preDp[i] = 1;
			 }
		 }
		 else if ('0' != s[0])
		 {
			 preDp[s[0] - '0'] = 1;
		 }

		 for (int i = 1; i < s.length(); i++)
		 {
			 vector<int> dp(27);
			 if ('*' == s[i])
			 {
				 for (int j = 1; j < 10; j++)
				 {
					 Test(dp, preDp, j);
				 }
			 }
			 else
			 {
				 Test(dp, preDp, s[i] - '0');
			 }
			 preDp.swap(dp);
		 }
		 int iRet = 0;
		 for (const auto& p : preDp)
		 {
			 CBigMath::AddAssignment(&iRet, p);
		 }
		 return iRet;
	 }
	 void Test(vector<int>& dp, const vector<int>& preDp, int iNum)
	 {
		 if (0 != iNum)
		 {
			 for (int i = 0; i < preDp.size(); i++)
			 {
				 CBigMath::AddAssignment(&dp[iNum], preDp[i]);
			 }
		 }
		 CBigMath::AddAssignment(&dp[10 + iNum], preDp[1]);
		 if (iNum <= 6)
		 {
			 CBigMath::AddAssignment(&dp[20 + iNum], preDp[2]);
		 }
	 }
 };

2023年1月第2版

class CBigMath
{
public:
static void AddAssignment(int* dst, const int& iSrc)
{
*dst = (dst + iSrc) % s_iMod;
}
static void AddAssignment(int dst, const int& iSrc, const int& iSrc1)
{
*dst = (*dst + iSrc) % s_iMod;
*dst = (dst + iSrc1) % s_iMod;
}
static void AddAssignment(int dst, const int& iSrc, const int& iSrc1, const int& iSrc2)
{
*dst = (*dst + iSrc) % s_iMod;
*dst = (*dst + iSrc1) % s_iMod;
*dst = (dst + iSrc2) % s_iMod;
}
static void SubAssignment(int dst, const int& iSrc)
{
*dst = (s_iMod - iSrc + *dst) % s_iMod;
}
static int Add(const int& iAdd1, const int& iAdd2)
{
return (iAdd1 + iAdd2) % s_iMod;
}
static int Mul(const int& i1, const int& i2)
{
return((long long)i1 *i2) % s_iMod;
}
private:
static const int s_iMod = 1000000007;
};

class Solution {
public:
int numDecodings(string s) {
vector preDp(27);
if (‘’ == s[0])
{
for (int i = 1; i < 10; i++)
{
preDp[i] = 1;
}
}
else if (‘0’ != s[0])
{
preDp[s[0] - ‘0’] = 1;
}
for (int i = 1; i < s.length(); i++)
{
vector dp(27);
if ('’ == s[i])
{
int iTotal = GetTotal(preDp);
for (int j = 1; j < 10; j++)
{
Test(dp, preDp, iTotal,j);
}
}
else
{
int iTotal = GetTotal(preDp);
Test(dp, preDp, iTotal,s[i] - ‘0’);
}
preDp.swap(dp);
}
return GetTotal(preDp);
}
int GetTotal(const vector& preDp)
{
int iRet = 0;
for (const auto& p : preDp)
{
CBigMath::AddAssignment(&iRet, p);
}
return iRet;
}
void Test(vector& dp, const vector& preDp,int iTotal, int iNum)
{
if (0 != iNum)
{
CBigMath::AddAssignment(&dp[iNum], iTotal);
}
CBigMath::AddAssignment(&dp[10 + iNum], preDp[1]);
if (iNum <= 6)
{
CBigMath::AddAssignment(&dp[20 + iNum], preDp[2]);
}
}
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/328583.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

轻量应用服务器Lighthouse_香港轻量服务器_海外轻量服务器-腾讯云

轻量应用服务器Lighthouse_香港轻量服务器_海外轻量服务器-腾讯云

腾讯云轻量应用服务器开箱即用、运维简单的轻量级云服务器&#xff0c;CPU内存带宽配置高并且价格特别便宜&#xff0c;大带宽&#xff0c;但是限制月流量&#xff0c;轻量2核2G3M带宽62元一年、2核2G4M优惠价118元一年&#xff0c;540元三年、2核4G5M带宽218元一年&#xff0c…
阅读更多...
spring常见漏洞（4）

spring常见漏洞（4）

CVE-2018-1270 Spring Messaging 命令执行漏洞(CVE-2018-1270)&#xff0c;Spring框架中的 spring-messaging 模块提供了一种基于WebSocket的STOMP协议实现&#xff0c;STOMP消息代理在处理客户端消息时存在SpEL表达式注入漏洞&#xff0c;攻击者可以通过构造恶意的消息来实现…
阅读更多...
汽车用螺纹紧固件的拧紧力矩规范主要考虑哪些方面——SunTorque智能扭矩系统

汽车用螺纹紧固件的拧紧力矩规范主要考虑哪些方面——SunTorque智能扭矩系统

在汽车制造过程中&#xff0c;螺纹紧固件是连接和固定各个零部件的重要元件。为了保证汽车的可靠性和安全性&#xff0c;对于螺纹紧固件的拧紧力矩有着严格的规定和规范。SunTorque智能扭矩系统和大家一起掌握这一重要知识点。 拧紧力矩是指将螺纹紧固件拧紧到预定位置所需的力…
阅读更多...
Vue创建项目配置情况

Vue创建项目配置情况

刚开始接触vue项目创建和运行因为node版本和插件版本不一致时长遇到刚装好插件&#xff0c;项目就跑不起来的情况&#xff0c;特此记录一下 vue -V vue/cli 5.0.8 node -v v12.22.12 npm -v 6.14.16 关闭驼峰命名检查、未使用语法检查 package.json文件内容&#xff1a; {&…
阅读更多...
0基础学习VR全景平台篇第138篇：无人机航拍实操

0基础学习VR全景平台篇第138篇：无人机航拍实操

上课&#xff01;全体起立~ 大家好&#xff0c;欢迎观看蛙色官方系列全景摄影课程&#xff01; 为了使全景的概念体现得更为广阔和大气&#xff0c;我们也需要在天空上运用无人机进行全景拍摄&#xff0c;而无人机的拍摄相对于地面来说也是较为简单&#xff0c;掌握其基本的拍…
阅读更多...
LeetCode 算法题 1.两数之和(python版)

LeetCode 算法题 1.两数之和(python版)

题目要求 给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数&#xff0c;并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是&#xff0c;数组中同一个元素在答案里不能重复出现。 代码 class…
阅读更多...
电路原理1-线性电阻

电路原理1-线性电阻

前言&#xff1a;整理笔记基于清华大学于歆杰老师的《电路原理》&#xff0c;电路原理是基于无源负载和电源组成电路的分析方法。 1.基础数学知识 算术&#xff1a;数字之间的运算 代数&#xff1a;用变量和函数来代替数字 微积分&#xff1a;描述函数的累积效应&#xff0…
阅读更多...
Facebook与环境保护：社交媒体的可持续发展

Facebook与环境保护：社交媒体的可持续发展

在当今社会&#xff0c;科技发展日新月异&#xff0c;而社交媒体作为数字时代的代表之一&#xff0c;正面临着巨大的责任与机遇。随着全球环境问题的凸显&#xff0c;社交媒体平台如Facebook也逐渐认识到自身在环保可持续发展中的角色。本文将深入探讨Facebook在环境保护方面的…
阅读更多...
2024“华数杯”国际大学生数学建模竞赛（B题）光伏发电| 建模秘籍文章代码思路大全

2024“华数杯”国际大学生数学建模竞赛（B题）光伏发电| 建模秘籍文章代码思路大全

铛铛&#xff01;小秘籍来咯&#xff01; 小秘籍希望大家都能轻松建模呀&#xff0c;华数杯也会持续给大家放送思路滴~ 抓紧小秘籍&#xff0c;我们出发吧~ 完整内容可以在文章末尾领取&#xff01; 问题重述 2024 "Huashu Cup"国际数学建模竞赛 ICM 问题 B: 太…
阅读更多...
四大软件架构：掌握单体、分布式、微服务、Serverless 的精髓

四大软件架构：掌握单体、分布式、微服务、Serverless 的精髓

四大软件架构&#xff1a;掌握单体、分布式、微服务、Serverless 的精髓 简介&#xff1a; 如果一个软件开发人员&#xff0c;不了解软件架构的演进&#xff0c;会制约技术的选型和开发人员的生存、晋升空间。这里我列举了目前主要的四种软件架构以及他们的优缺点&#xff0c;…
阅读更多...
翼龙-2H无人机

翼龙-2H无人机

一、概述 翼龙-2&#xff0c;是成都飞机工业集团研制的无人驾驶飞行器&#xff0c;是空中侦察、精确打击和应急通讯的平台。成都飞机工业集团于2015年9月的北京国际航空航天展览会上介绍了翼龙-2的概念。在2016年珠海航展期间&#xff0c;翼龙-2的原型机首次向公众展示。 因为…
阅读更多...
selenium+java 通过classname定位时中间有空格解决办法

selenium+java 通过classname定位时中间有空格解决办法

1、如图所示&#xff0c;class"main-table-span title" 中有空格 如果直接通过 driver.findElement(By.classname(".main-table-span title"));来进行定位界面会出现报错 2、可以在classname的前面和空格处用.号代替通过css来定位&#xff0c;如下&#…
阅读更多...
c# 视频播放之Windows Media Player

c# 视频播放之Windows Media Player

最近想给软件加个视频播放功能&#xff0c;在网上看有好几个方式&#xff0c;最后决定用 Windows Media Player 和Vlc.DotNet.Forms。 这篇文章主要讲Windows Media Player&#xff0c;它的优点&#xff1a;代码简单&#xff0c;视频操作功能都有&#xff0c;能播放网络和本地…
阅读更多...
一场特别的捐赠活动，一份来自“远方”的温暖

一场特别的捐赠活动，一份来自“远方”的温暖

1月12日&#xff0c;一场特别的捐赠仪式在青海省玉树州玉树市隆宝镇中心寄宿制学校举行。这所处在海拔4300多米、年均气温在零度以下高寒地区小学中的813名孩子&#xff0c;在这天收到了来自“远方”的祝福与温暖。 捐赠现场 12月22日&#xff0c;由北京演艺集团出品、北京歌剧…
阅读更多...
2024年“华数杯”国际大学生数学建模竞赛B题思路

2024年“华数杯”国际大学生数学建模竞赛B题思路

本题难点在于数据获取和定性定量分析&#xff0c;代码部分没有太大价值、就不更新了 •中国的电力供应和许多因素相互作用。请研究它们之间的关系&#xff0c;并预测2024年至2060年中国电力供应的发展趋势。 首先得获取数据&#xff0c;中国的宏观数据相对容易&#xff08;包括…
阅读更多...
C++中map按照从大到小的顺序存储元素

C++中map按照从大到小的顺序存储元素

map按照从大到小存储元素 引言map的大致介绍概述 场景误区示例示例代码&#xff08;方法一&#xff09;运行结果示例代码二&#xff08;方法二&#xff09;运行结果 引言 在对map的使用中&#xff0c;由于对业务的需要&#xff0c;希望map中存储元素能够按照键的大小从大到小的…
阅读更多...
跟着pink老师前端入门教程-day03

跟着pink老师前端入门教程-day03

6. 表格标签 6.1 表格的主要作用 主要用于显示、展示数据&#xff0c;可以让数据显示的规整&#xff0c;可读性非常好&#xff0c;特别是后台展示数据时&#xff0c;能够熟练运用表格就显得很重要。 6.2 基本语法 <!--1. <table> </table> 是用于定义表格的标…
阅读更多...
别找进销存试用版了，直接送你一个免费的

别找进销存试用版了，直接送你一个免费的

很多朋友在找进销存的试用版&#xff0c;花了大量的时间找&#xff0c;找到了可能也只能用一两个月。我发现了一个免费的&#xff0c;直接送给你们。 这是一个大平台的引流系统&#xff0c;吸引客户用的&#xff0c;但是我们不管他&#xff0c;我们就直接用就行了。我已经用了…
阅读更多...
echarts通过dataZoom实现单击图像滑动

echarts通过dataZoom实现单击图像滑动

实现原理; 1.option中配置初始化的dataZoom属性&#xff0c;并确定初始化数据展现位置 2.通过graphic属性配置图标及文本&#xff0c;并添加点击事件onclick&#xff1b; 3.通过dispatchAction的type: ‘dataZoom’&#xff0c;实现数据的最终展现。 效果&#xff1a;点击1图标…
阅读更多...
定制聚四氟乙烯溢流釜出图灵活加工

定制聚四氟乙烯溢流釜出图灵活加工

您提供想法&#xff0c;我们负责实现。
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站