数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学C++实现的学生出勤记录II
假设我们有一个正整数n，我们需要找到长度为n的所有可能的、被认为是合格的出勤记录的数量。由于答案可能非常大，我们将使用模109 + 7的结果进行返回。
在学生出勤记录中，字符串只能包含以下三个字符：
- 'A' 表示缺席。
- 'L' 表示迟到。
- 'P' 表示出席。
如果一个出勤记录不包含多于一个'A'（缺席）或多于两个连续的'L'（迟到），则该出勤记录被视为合格的。所以我们需要找到合格记录的最大数量。
如果输入是2，则输出将是8，因为我们可以生成8种可能的合格方式，它们是[PP, AP, PA, LP, PL, AL, LA, LL]，只有AA不会出现。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个函数add()，它将接收a，b，
- 返回((a mod m) + (b mod m)) mod m
- 从主方法中，执行以下操作：
- 定义一个大小为n + 1的数组p，大小为n + 1的数组a，大小为n + 1的数组l，大小为n + 1的数组ap和大小为n + 1的数组al
- 如果n等于1，则：
- 返回3
- p[0] := 1, p[1] := 1, p[2] := 3
- a[0] := 1, a[1] := 1, a[2] := 2
- l[0] := 1, l[1] := 1, l[2] := 3
- ap[0] := 1, ap[1] := 1, ap[2] := 2
- al[0] := 1, al[1] := 1, al[2] := 2
- 对于初始化i := 3，当i <= n，更新（i增加1），执行：
- p[i] := add(add(p[i - 1], a[i - 1]), l[i - 1])
- l[i] := add(add(p[i - 1], p[i - 2]), add(a[i - 1], a[i - 2]))
- a[i] := add(al[i - 1], ap[i - 1])
- al[i] := add(ap[i - 1], ap[i - 2])
- ap[i] := add(ap[i - 1], al[i - 1])
- 返回add(add(p[n], l[n]), a[n])
让我们来看下面的实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return ( (a % m) + (b % m) ) % m;
}
int checkRecord(int n) {
vector <int> p(n+1), a(n+1), l(n+1), ap(n+1), al(n+1);
if(n == 1)return 3;
p[0] = 1;
p[1] = 1;
p[2] = 3;
a[0] = 1;
a[1] = 1;
a[2] = 2;
l[0] = 1;
l[1] = 1;
l[2] = 3;
ap[0] = 1;
ap[1] = 1;
ap[2] = 2;
al[0] = 1;
al[1] = 1;
al[2] = 2;
for(int i = 3; i <= n; i++){
p[i] = add(add(p[i-1], a[i-1]), l[i-1]);
l[i] = add(add(p[i-1], p[i-2]),add(a[i-1] , a[i-2]));
a[i] = add(al[i-1], ap[i-1]);
al[i] = add(ap[i-1], ap[i-2]);
ap[i] = add(ap[i-1], al[i-1]);
}
return add(add(p[n], l[n]), a[n]);
}
};
main(){
Solution ob;
cout << (ob.checkRecord(3));
}输入
3
输出
19
更新于：2020年6月1日
490 次查看
广告