【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II

简介: 【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II

LeetCode552. 学生出勤记录 II

可以用字符串表示一个学生的出勤记录,其中的每个字符用来标记当天的出勤情况(缺勤、迟到、到场)。记录中只含下面三种字符:

‘A’:Absent,缺勤

‘L’:Late,迟到

‘P’:Present,到场

如果学生能够 同时 满足下面两个条件,则可以获得出勤奖励:

按 总出勤 计,学生缺勤(‘A’)严格 少于两天。

学生 不会 存在 连续 3 天或 连续 3 天以上的迟到(‘L’)记录。

给你一个整数 n ,表示出勤记录的长度(次数)。请你返回记录长度为 n 时,可能获得出勤奖励的记录情况 数量 。答案可能很大,所以返回对 109 + 7 取余 的结果。

示例 1:

输入:n = 2

输出:8

解释:

有 8 种长度为 2 的记录将被视为可奖励:

“PP” , “AP”, “PA”, “LP”, “PL”, “AL”, “LA”, “LL”

只有"AA"不会被视为可奖励,因为缺勤次数为 2 次(需要少于 2 次)。

示例 2:

输入:n = 1

输出:3

示例 3:

输入:n = 10101

输出:183236316

提示:

1 <= n <= 105

动态规划

时间复杂度: O(n)

计算第k天,只需要知道第k-1天的情况,所以可以用滚动向量。

注意: 连续迟到,值包括迟到,不包括缺勤。虽然缺勤更严重。

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

动态规划的状态表示 pre[i][j]表示,第k-1天,缺勤i次,i-1天起,连续迟到j天的可能数量。
动态规划的转移方程 见下文
动态规划的初始状态 pre[0][0]=1
动态规划的填表顺序 天数k从小到大,确保动态规划的无后效性
动态规划的返回值 pre[i][j]的和

动态规划的转移方程

今天正常(到场):不淘汰,缺勤数量不边,连续迟到清0。

今天缺勤:淘汰已经缺勤1次的。缺勤次数+1,连续迟到清0。

今天迟到:淘汰已经迟到2次的。缺勤次数不边,迟到次数+1。

代码

核心代码

class Solution {
public:
  int checkRecord(int n) {
    vector<vector<C1097Int<>>> pre(2, vector<C1097Int<>>(3));
    pre[0][0] = 1;//缺勤0次,结尾迟到0次
    while(n--)
    {
      vector<vector<C1097Int<>>> dp(2, vector<C1097Int<>>(3));
      //处理到场
      for (int i = 0; i < 2; i++)
      {
        dp[i][0] += std::accumulate(pre[i].begin(), pre[i].end(), C1097Int<>());
      }
      //处理缺勤
      dp[1][0] += std::accumulate(pre[0].begin(), pre[0].end(), C1097Int<>());
      //处理迟到
      for (int i = 0; i < 2; i++)
      {
        for (int j = 0; j < 2; j++)
        {
          dp[i][j + 1] += pre[i][j];
        }
      }
      pre.swap(dp);
    }
    C1097Int<> biRet = std::accumulate(pre[0].begin(), pre[0].end(), C1097Int<>())
      + std::accumulate(pre[1].begin(), pre[1].end(), C1097Int<>());
    return biRet.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()
{
  int n;
  {
    Solution sln;
    n = 2;
    auto res = sln.checkRecord(n);
    Assert(8, res);
  }
  {
    Solution sln;
    n = 1;
    auto res = sln.checkRecord(n);
    Assert(3, res);
  }
  {
    Solution sln;
    n = 10101;
    auto res = sln.checkRecord(n);
    Assert(183236316, res);
  }
}

2023年1月

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 checkRecord(int n) {
//preDp[i][j]表示缺勤i天,最后一天连续j天迟到
vector preDp;
preDp.assign(2, vector(3));
preDp[0][0] = 1;
for (int i = 0; i < n; i++)
{
vector dp;
dp.assign(2, vector(3));
//正常通勤
CBigMath::AddAssignment(&dp[0][0], preDp[0][0], preDp[0][1], preDp[0][2]);
CBigMath::AddAssignment(&dp[1][0], preDp[1][0], preDp[1][1], preDp[1][2]);
//缺勤
CBigMath::AddAssignment(&dp[1][0], preDp[0][0], preDp[0][1], preDp[0][2]);
//迟到
for (int j = 0; j < 2; j++)
{
for (int k = 0; k < 2; k++)
{
CBigMath::AddAssignment(&dp[j][k + 1], preDp[j][k]);
}
}
preDp.swap(dp);
}
int iRet = 0;
   for (int i = 0; i < preDp.size(); i++)
   {
     for (int j = 0; j < preDp[i].size(); j++)
     {
       CBigMath::AddAssignment(&iRet, preDp[i][j]);
     }
   }
   return iRet;
 }

};


扩展阅读

视频课程

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

相关文章
|
1月前
|
运维 监控 算法
解读 C++ 助力的局域网监控电脑网络连接算法
本文探讨了使用C++语言实现局域网监控电脑中网络连接监控的算法。通过将局域网的拓扑结构建模为图(Graph)数据结构,每台电脑作为顶点,网络连接作为边,可高效管理与监控动态变化的网络连接。文章展示了基于深度优先搜索(DFS)的连通性检测算法,用于判断两节点间是否存在路径,助力故障排查与流量优化。C++的高效性能结合图算法,为保障网络秩序与信息安全提供了坚实基础,未来可进一步优化以应对无线网络等新挑战。
|
1月前
|
存储 负载均衡 算法
基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
在局域网计算机管理中,迪杰斯特拉算法用于优化网络路径、分配资源和定位故障节点,确保高效稳定的网络环境。该算法通过计算最短路径,提升数据传输速率与稳定性,实现负载均衡并快速排除故障。C++代码示例展示了其在网络模拟中的应用,为企业信息化建设提供有力支持。
64 15
|
1月前
|
存储 算法 数据处理
公司局域网管理中的哈希表查找优化 C++ 算法探究
在数字化办公环境中,公司局域网管理至关重要。哈希表作为一种高效的数据结构,通过哈希函数将关键值(如IP地址、账号)映射到数组索引,实现快速的插入、删除与查找操作。例如,在员工登录验证和设备信息管理中,哈希表能显著提升效率,避免传统线性查找的低效问题。本文以C++为例,展示了哈希表在局域网管理中的具体应用,包括设备MAC地址与IP分配的存储与查询,并探讨了优化哈希函数和扩容策略,确保网络管理高效准确。
|
9天前
|
存储 监控 算法
基于 C++ 哈希表算法的局域网如何监控电脑技术解析
当代数字化办公与生活环境中,局域网的广泛应用极大地提升了信息交互的效率与便捷性。然而,出于网络安全管理、资源合理分配以及合规性要求等多方面的考量,对局域网内计算机进行有效监控成为一项至关重要的任务。实现局域网内计算机监控,涉及多种数据结构与算法的运用。本文聚焦于 C++ 编程语言中的哈希表算法,深入探讨其在局域网计算机监控场景中的应用,并通过详尽的代码示例进行阐释。
30 4
|
19天前
|
存储 算法 安全
企业员工数据泄露防范策略:基于 C++ 语言的布隆过滤器算法剖析[如何防止员工泄密]
企业运营过程中,防范员工泄密是信息安全领域的核心议题。员工泄密可能致使企业核心数据、商业机密等关键资产的流失,进而给企业造成严重损失。为应对这一挑战,借助恰当的数据结构与算法成为强化信息防护的有效路径。本文专注于 C++ 语言中的布隆过滤器算法,深入探究其在防范员工泄密场景中的应用。
37 8
|
2月前
|
存储 算法 Java
算法系列之动态规划
动态规划(Dynamic Programming,简称DP)是一种用于解决复杂问题的算法设计技术。它通过将问题分解为更小的子问题,并存储这些子问题的解来避免重复计算,从而提高算法的效率。
81 4
算法系列之动态规划
|
2月前
|
存储 监控 算法
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
38 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
|
2月前
|
算法 安全 调度
【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码
【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码
|
2月前
|
机器学习/深度学习 算法 测试技术
【动态规划篇】01 背包的逆袭:如何用算法装满你的 “财富背包”
【动态规划篇】01 背包的逆袭:如何用算法装满你的 “财富背包”
|
2月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。

热门文章

最新文章