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

本文主要是介绍【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

作者推荐

【动态规划】458:可怜的小猪

本题其它解法

【矩阵快速幂】封装类及测试用例及样例 预计2024年1月15(周一7:00)发布

涉及知识点

动态规划 矩阵快速幂 滚动向量

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<vector> preDp;
preDp.assign(2, vector(3));
preDp[0][0] = 1;
for (int i = 0; i < n; i++)
{
vector<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++**实现。

这篇关于【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

一文详解如何在idea中快速搭建一个Spring Boot项目

《一文详解如何在idea中快速搭建一个SpringBoot项目》IntelliJIDEA作为Java开发者的‌首选IDE‌,深度集成SpringBoot支持,可一键生成项目骨架、智能配置依赖,这篇文... 目录前言1、创建项目名称2、勾选需要的依赖3、在setting中检查maven4、编写数据源5、开启热

C++中RAII资源获取即初始化

《C++中RAII资源获取即初始化》RAII通过构造/析构自动管理资源生命周期,确保安全释放,本文就来介绍一下C++中的RAII技术及其应用,具有一定的参考价值,感兴趣的可以了解一下... 目录一、核心原理与机制二、标准库中的RAII实现三、自定义RAII类设计原则四、常见应用场景1. 内存管理2. 文件操

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri

C++高效内存池实现减少动态分配开销的解决方案

《C++高效内存池实现减少动态分配开销的解决方案》C++动态内存分配存在系统调用开销、碎片化和锁竞争等性能问题,内存池通过预分配、分块管理和缓存复用解决这些问题,下面就来了解一下... 目录一、C++内存分配的性能挑战二、内存池技术的核心原理三、主流内存池实现:TCMalloc与Jemalloc1. TCM

Python UV安装、升级、卸载详细步骤记录

《PythonUV安装、升级、卸载详细步骤记录》:本文主要介绍PythonUV安装、升级、卸载的详细步骤,uv是Astral推出的下一代Python包与项目管理器,主打单一可执行文件、极致性能... 目录安装检查升级设置自动补全卸载UV 命令总结 官方文档详见:https://docs.astral.sh/

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五

统一返回JsonResult踩坑的记录

《统一返回JsonResult踩坑的记录》:本文主要介绍统一返回JsonResult踩坑的记录,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录统一返回jsonResult踩坑定义了一个统一返回类在使用时,JsonResult没有get/set方法时响应总结统一返回

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域(Scope)和标识符查找(IdentifierLookup)是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找(Ordinary Lookup)2. 限定查找(Qualif

Go学习记录之runtime包深入解析

《Go学习记录之runtime包深入解析》Go语言runtime包管理运行时环境,涵盖goroutine调度、内存分配、垃圾回收、类型信息等核心功能,:本文主要介绍Go学习记录之runtime包的... 目录前言:一、runtime包内容学习1、作用:① Goroutine和并发控制:② 垃圾回收:③ 栈和

html 滚动条滚动过快会留下边框线的解决方案

《html滚动条滚动过快会留下边框线的解决方案》:本文主要介绍了html滚动条滚动过快会留下边框线的解决方案,解决方法很简单,详细内容请阅读本文,希望能对你有所帮助... 滚动条滚动过快时,会留下边框线但其实大部分时候是这样的,没有多出边框线的滚动条滚动过快时留下边框线的问题通常与滚动条样式和滚动行