AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

2024-01-22 58
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【动态规划】【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]jdp[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++**实现。

文章标签：
云数据库 ClickHouse
算法
C++
测试技术
C#
关键词：
算法方法
算法动态规划
动态规划算法
C++算法
算法c++
闻缺陷则喜何志丹
目录
相关文章
龙大吉
|
29天前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法，通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法，通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理，包括初始化、数据点分配与簇中心更新等步骤，以及如何在Python中实现该算法，最后讨论了其优缺点及应用场景。
龙大吉
96 4
众所周知
|
2月前
|
存储 算法 Java
解析HashSet的工作原理，揭示Set如何利用哈希算法和equals()方法确保元素唯一性，并通过示例代码展示了其“无重复”特性的具体应用
在Java中，Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理，揭示Set如何利用哈希算法和equals()方法确保元素唯一性，并通过示例代码展示了其“无重复”特性的具体应用。
众所周知
56 3
小宋1021
|
27天前
|
存储 算法 安全
SnowflakeIdGenerator-雪花算法id生成方法
SnowflakeIdGenerator-雪花算法id生成方法
小宋1021
23 1
龙大吉
|
1月前
|
算法 Python
在Python编程中，分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题，递归解决后合并结果
在Python编程中，分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题，递归解决后合并结果；贪心算法在每一步选择局部最优解，追求全局最优；动态规划通过保存子问题的解，避免重复计算，确保全局最优。这三种算法各具特色，适用于不同类型的问题，合理选择能显著提升编程效率。
龙大吉
53 2
java冯坚持
|
2月前
|
算法
动态规划算法学习三：0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解，包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
java冯坚持
104 2
动态规划算法学习三：0-1背包问题
路人与大师
|
1月前
|
JSON 算法 数据挖掘
基于图论算法有向图PageRank与无向图Louvain算法构建指令的方式方法 用于支撑qwen agent中的统计相关组件
利用图序列进行数据解读，主要包括节点序列分析、边序列分析以及结合节点和边序列的综合分析。节点序列分析涉及节点度分析（如入度、出度、度中心性）、节点属性分析（如品牌、价格等属性的分布与聚类）、节点标签分析（如不同标签的分布及标签间的关联）。边序列分析则关注边的权重分析（如关联强度）、边的类型分析（如管理、协作等关系）及路径分析（如最短路径计算）。结合节点和边序列的分析，如子图挖掘和图的动态分析，可以帮助深入理解图的结构和功能。例如，通过子图挖掘可以发现具有特定结构的子图，而图的动态分析则能揭示图随时间的变化趋势。这些分析方法结合使用，能够从多个角度全面解读图谱数据，为决策提供有力支持。
路人与大师
95 0
Dylaniou
|
2月前
|
算法 索引
HashMap扩容时的rehash方法中(e.hash & oldCap) == 0算法推导
HashMap在扩容时，会创建一个新数组，并将旧数组中的数据迁移过去。通过(e.hash & oldCap)是否等于0，数据被巧妙地分为两类：一类保持原有索引位置，另一类索引位置增加旧数组长度。此过程确保了数据均匀分布，提高了查询效率。
Dylaniou
48 2
java冯坚持
|
2月前
|
算法
动态规划算法学习四：最大上升子序列问题（LIS：Longest Increasing Subsequence）
这篇文章介绍了动态规划算法中解决最大上升子序列问题（LIS）的方法，包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法，如非动态规划的二分法。
java冯坚持
80 0
动态规划算法学习四：最大上升子序列问题（LIS：Longest Increasing Subsequence）
ephemerals__
|
29天前
|
存储 编译器 C语言
【c++丨STL】string类的使用
本文介绍了C++中`string`类的基本概念及其主要接口。`string`类在C++标准库中扮演着重要角色，它提供了比C语言中字符串处理函数更丰富、安全和便捷的功能。文章详细讲解了`string`类的构造函数、赋值运算符、容量管理接口、元素访问及遍历方法、字符串修改操作、字符串运算接口、常量成员和非成员函数等内容。通过实例演示了如何使用这些接口进行字符串的创建、修改、查找和比较等操作，帮助读者更好地理解和掌握`string`类的应用。
ephemerals__
50 2
ephemerals__
|
1月前
|
存储 编译器 C++
【c++】类和对象（下）（取地址运算符重载、深究构造函数、类型转换、static修饰成员、友元、内部类、匿名对象）
本文介绍了C++中类和对象的高级特性，包括取地址运算符重载、构造函数的初始化列表、类型转换、static修饰成员、友元、内部类及匿名对象等内容。文章详细解释了每个概念的使用方法和注意事项，帮助读者深入了解C++面向对象编程的核心机制。
ephemerals__
103 5

热门文章

最新文章

  • 1
    机器学习-特征选择：如何使用递归特征消除算法自动筛选出最优特征？
  • 2
    领域最全 | 计算机视觉算法在路面坑洼检测中的应用综述(基于2D图像/3D LiDAR/深度学习)（上）
  • 3
    【WSN定位】基于chan算法实现多基站目标定位附Matlab代码
  • 4
    openssl中算法的组织方式
  • 5
    OpenCV 1 图像分割--分水岭算法代码
  • 6
    Linux内核中的有关Page的算法
  • 7
    缓存、缓存算法(转)
  • 8
    算法笔记之回溯法（2）
  • 9
    图解算法：摘取位运算的王冠「八皇后问题」！| 算法必看系列十七
  • 10
    Console-算法[for]-输出等腰三角形
  • 1
    c++引用是什么意思？
    49
  • 2
    C++ 多态 虚函数和纯虚函数
    51
  • 3
    C++ 重载运算符和重载函数
    51
  • 4
    C++ 类构造函数 & 析构函数
    51
  • 5
    C++ this 指针详解
    44
  • 6
    C++友元函数和友元类
    54
  • 7
    从C++看编程语言发展脉络
    118
  • 8
    LabVIEW使用Python MathWorks® MATLAB®软件和C/C++
    72
  • 9
    LabVIEW传递接收C/C++DLL指针
    209
  • 10
    LabVIEW调用C/C++ DLLs
    134

    • 相关课程

    更多
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • C++ 入门教程开发文档
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    DataWorks售前咨询