C++前缀和算法的应用:DI序列的有效排列的原理、源码及测试用例

简介: C++前缀和算法的应用:DI序列的有效排列的原理、源码及测试用例

本文涉及的基础知识点

C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

题目

给定一个长度为 n 的字符串 s ,其中 s[i] 是:

“D” 意味着减少,或者

“I” 意味着增加

有效排列 是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm ,使得对所有的 i:

如果 s[i] == ‘D’,那么 perm[i] > perm[i+1],以及;

如果 s[i] == ‘I’,那么 perm[i] < perm[i+1]。

返回 有效排列 perm的数量 。因为答案可能很大,所以请返回你的答案对 109 + 7 取余。

示例 1:

输入:s = “DID”

输出:5

解释:

(0, 1, 2, 3) 的五个有效排列是:

(1, 0, 3, 2)

(2, 0, 3, 1)

(2, 1, 3, 0)

(3, 0, 2, 1)

(3, 1, 2, 0)

示例 2:

输入: s = “D”

输出: 1

分析

用动态规划解决,时间复杂度O(nnn)。用strRes表示结果串,用n表示它的长度,每个数字的取值范围[0,n)。dp[i][j],表示前i+1个数已经处理,未处理的数中共有j个数大于strRes[i]。状态数共有n*n个,状态转换的时间复杂是O(n)。以上升为例:只需要考虑j个比strRes[i]数,选择最小的数,则jNew=j-1;选择次小的数, jNew=j-2…。下降类似,小于strRes[i]的数,可以计算出来:总数-已经处理的数-未处理的数中大于res[i]=n-(i+1)-j。注意:各位数各不相等,所以已经处理的数(如:res[i])是不会在出现的,所以未处理的数,需要考虑大于和小于,不需要考虑等于。

代码

template
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;;
};
template
int operator+(int iData, const C1097Int& int1097)
{
int iRet = int1097.operator+(C1097Int(iData)).ToInt();
return iRet;
}
template
int& operator+=(int& iData, const C1097Int& int1097)
{
iData = int1097.operator+(C1097Int(iData)).ToInt();
return iData;
}
template
int operator*(int iData, const C1097Int& int1097)
{
int iRet = int1097.operator*(C1097Int<>(iData)).ToInt();
return iRet;
}
template
int& operator*=(int& iData, const C1097Int& int1097)
{
iData = int1097.operator*(C1097Int<>(iData)).ToInt();
return iData;
}
class Solution {
public:
  int numPermsDISequence(string s) {
    //n:结果串的长度 每个数字的取值范围[0,n)
    int n = s.length() + 1;
    vector<C1097Int<>> pre(n);//记录有多少个数大于当前数
    for (int i = 0; i < n; i++)
    {
      pre[n - i -1] += 1;
    }
    for (int i = 0; i < s.length(); i++)
    {
      vector<C1097Int<>> dp(n );
      if ('I' == s[i])
      {
        for (int iMore = 1; iMore < n; iMore++)
        {
          for (int j = 0; j < iMore; j++)
          {
            dp[iMore - j - 1] += pre[iMore];
          }
        }
      }
      else
      {
        for (int iMore = 0; iMore < n; iMore++)
        {
          const int less = n - (i + 1) - iMore;
          if (less < 1)
          {
            break;
          }
          for (int j = 0; j < less; j++)
          {
            const int iNewLess = less - j - 1;
            const int iNewMore = n - (i + 1 + 1) - iNewLess;
            dp[iNewMore] += pre[iMore];
          }
        }
      }
      pre.swap(dp);
    }
    auto bi = std::accumulate(pre.begin(), pre.end(), C1097Int<>(0));
    return bi.ToInt();
  }
};

测试用例

int main()
{
int res = Solution().numPermsDISequence(“”);
Assert(1, res);
res = Solution().numPermsDISequence(“I”);
Assert(1, res);
res = Solution().numPermsDISequence(“D”);
Assert(1, res);
res = Solution().numPermsDISequence(“II”);
Assert(1, res);
res = Solution().numPermsDISequence(“ID”);
Assert(2, res);
res = Solution().numPermsDISequence(“DD”);
Assert(1, res);
res = Solution().numPermsDISequence(“DI”);
Assert(2, res);
res = Solution().numPermsDISequence(“DID”);
Assert(5, res);
res = Solution().numPermsDISequence(“IDD”);
Assert(3, res);
res = Solution().numPermsDISequence(“DDI”);
Assert(3, res);
res = Solution().numPermsDISequence(“DII”);
Assert(3, res);
res = Solution().numPermsDISequence(“IDI”);
Assert(5, res);
res = Solution().numPermsDISequence(“IID”);
Assert(3, res);
//CConsole::Out(res);
}

优化

可以利用前缀和,将时间复杂度降到O(n*n)。

iMore取[1,…]中任意数,选择最大的数,则jNew都等于0
iMore取[2,…]中任意数,选择次大的数,则jNew都等于1
iMore取[3,…] 中任意数,选择第三大的数,则jNew都等于2
结论:
dp[0] = sum(pre[1]…pre[n-1])
dp[1] = sum(pre[2]…pre[n-1])
dp[2] = sum(pre[3]…pre[n-1])

代码

class Solution {
public:
  int numPermsDISequence(string s) {
    //n:结果串的长度 每个数字的取值范围[0,n)
    int n = s.length() + 1;
    vector<C1097Int<>> pre(n);//记录有多少个数大于当前数
    for (int i = 0; i < n; i++)
    {
      pre[n - i -1] += 1;
    }
    for (int i = 0; i < s.length(); i++)
    {
      vector<C1097Int<>> dp(n );
      if ('I' == s[i])
      {
        C1097Int<> biSum = 0;
        for (int j = n-1; j > 0 ; j-- )
        {
          biSum += pre[j];
          dp[j-1] = biSum;
        }
      }
      else
      {
        C1097Int<> biSum = 0;
        for (int j = n - 1; j > 0; j--)
        {//j是小于strRes[i]的数目
          const int iMore = n - (i + 1) - j;
          if (iMore < 0)
          {
            continue;
          }
          const int iNewMore = n - (i + 1+1) - (j-1);
          biSum += pre[iMore];
          dp[iNewMore] = biSum;
        }
      }
      pre.swap(dp);
    }
    auto bi = std::accumulate(pre.begin(), pre.end(), C1097Int<>(0));
    return bi.ToInt();
  }
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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


相关文章
|
6天前
|
机器学习/深度学习 算法 计算机视觉
YOLOv3的算法原理是怎么样的
YOLOv3的算法原理是怎么样的
|
7天前
|
编译器 C++ 容器
C++模板的原理及使用
C++模板的原理及使用
|
8天前
|
算法 安全 网络协议
https原理--RSA密钥协商算法
https原理--RSA密钥协商算法
17 0
|
8天前
|
机器学习/深度学习 编解码 算法
算法工程师面试问题总结 | YOLOv5面试考点原理全解析
本文给大家带来的百面算法工程师是深度学习目标检测YOLOv5面试总结,文章内总结了常见的提问问题,旨在为广大学子模拟出更贴合实际的面试问答场景。在这篇文章中,我们还将介绍一些常见的深度学习目标检测面试问题,并提供参考的回答及其理论基础,以帮助求职者更好地准备面试。通过对这些问题的理解和回答,求职者可以展现出自己的深度学习目标检测领域的专业知识、解决问题的能力以及对实际应用场景的理解。同时,这也是为了帮助求职者更好地应对深度学习目标检测岗位的面试挑战,提升面试的成功率和竞争力。
|
13天前
|
设计模式 算法 C++
【C++】STL之迭代器介绍、原理、失效
【C++】STL之迭代器介绍、原理、失效
20 2
|
13天前
|
负载均衡 算法 调度
负载均衡原理及算法
负载均衡原理及算法
17 1
|
13天前
|
Arthas 监控 算法
JVM工作原理与实战(二十五):堆的垃圾回收-垃圾回收算法
JVM作为Java程序的运行环境,其负责解释和执行字节码,管理内存,确保安全,支持多线程和提供性能监控工具,以及确保程序的跨平台运行。本文主要介绍了垃圾回收算法评价标准、标记清除算法、复制算法、标记整理算法、分代垃圾回收算法等内容。
27 0
JVM工作原理与实战(二十五):堆的垃圾回收-垃圾回收算法
|
13天前
|
存储 机器学习/深度学习 人工智能
c/c++线性表实现附源码(超详解)
c/c++线性表实现附源码(超详解)
18 0
|
13天前
|
机器学习/深度学习 自然语言处理 算法
机器学习算法原理与应用:深入探索与实战
【5月更文挑战第2天】本文深入探讨机器学习算法原理,包括监督学习(如线性回归、SVM、神经网络)、非监督学习(聚类、PCA)和强化学习。通过案例展示了机器学习在图像识别(CNN)、自然语言处理(RNN/LSTM)和推荐系统(协同过滤)的应用。随着技术发展,机器学习正广泛影响各领域,但也带来隐私和算法偏见问题,需关注解决。
|
13天前
|
算法 数据安全/隐私保护 计算机视觉
基于二维CS-SCHT变换和LABS方法的水印嵌入和提取算法matlab仿真
该内容包括一个算法的运行展示和详细步骤,使用了MATLAB2022a。算法涉及水印嵌入和提取,利用LAB色彩空间可能用于隐藏水印。水印通过二维CS-SCHT变换、低频系数处理和特定解码策略来提取。代码段展示了水印置乱、图像处理(如噪声、旋转、剪切等攻击)以及水印的逆置乱和提取过程。最后,计算并保存了比特率,用于评估水印的稳健性。