LeetCode刷题实战552：学生出勤记录 II

本文主要是介绍LeetCode刷题实战552：学生出勤记录 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 学生出勤记录 II，我们先来看题面：

https://leetcode-cn.com/problems/student-attendance-record-ii/

You are given a string s representing an attendance record for a student where each character signifies whether the student was absent, late, or present on that day. The record only contains the following three characters:

'A': Absent.
'L': Late.
'P': Present.

The student is eligible for an attendance award if they meet both of the following criteria:

The student was absent ('A') for strictly fewer than 2 days total.
The student was never late ('L') for 3 or more consecutive days.

Given an integer n, return the number of possible attendance records of length n that make a student eligible for an attendance award. The answer may be very large, so return it modulo 109 + 7.

给你一个字符串 s 表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：

'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

解题

https://www.jianshu.com/p/ac5eb0474f7a

输入 n 代表的是天数，我每天去上学，有三种结果：准时 P，缺席 P，迟到 L。如果我 n 天后没有缺席超过一次（严格少于 2 天），且没有连续超过两天迟到，则我可以拿到奖励。

我在 1 - n 中的任何一天，是否有可能拿到奖励，取决于我过去的日子的上学情况，例如：

例 1：如果今天缺席了，而我过去某一天也缺席了，则我一定无法最终拿到奖励；

例 2：如果今天缺席了，我过去每一天都是好学生，一次缺席也没有，一次迟到也没有，那我今天缺席一次没啥嘛，之后好好表现还是有可能拿到奖励。

这样就是从小问题可以推导出大问题，用动态规划解。

dp[i][j][k] 等于第 i 天，在过去缺席了 j 次，以及连续迟到了 k 次的情况下，还可以拿到奖励的出席排列的数量。随着天数的增加，这个 dp 的值肯定是递减的，因为搞不好未来哪一天就缺席或者迟到再也拿不到奖励了。

j 一共有两种可能，0 或者 1 ，对应不能缺席超过 1 次。k 一共有三种可能：0,1,2，对应不能连续迟到超过 2 次。

今天：缺席、不缺席、连续迟到天数

dp[天数][缺席][连续迟到] 一共有六种：

dp[i][0][0]：今天截止 0 次缺席，今天截止 0 天连续迟到。

dp[i][0][1]：今天截止 0 次缺席，今天截止 1 天连续迟到。

dp[i][0][2]：今天截止 0 次缺席，今天截止 2 天连续迟到。

dp[i][1][0]：今天截止 1 次缺席，今天截止 0 天连续迟到。

dp[i][1][1]：今天截止 1 次缺席，今天截止 1 天连续迟到。

dp[i][1][2]：今天截止 1 次缺席，今天截止 2 天连续迟到。

我们依次分析六种情况：

情况 1：今天截止 0 次缺席，今天截止 0 次连续迟到：

dp[i][0][0] = dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]

说明：「今天截止 0 次缺席」说明今天出席。

过去一定也是 0 次缺席，但过去可以有 0，1，2 次连续迟到；

只要今天按时出席，过去的迟到记录都一笔勾销。

情况 2：今天截止 1 次缺席，今天截止 0 次连续迟到：

dp[i][1][0] = dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][1][2] + dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]

分两种情况：

前三项，代表过去有 1 次缺席，今天没有缺席，但过去可以有 0、1、2 次连续迟到，过去的迟到记录都一笔勾销。

后三项，代表过去有 0 次缺席，今天缺席了，但过去可以有 0、1、2 次连续迟到，过去的迟到记录都一笔勾销。

情况 3：今天截止 0 次缺席，今天截止 1 次连续迟到：

dp[i][0][1] = dp[i - 1][0][0];

过去 0 次缺席，过去 0 次迟到，今天迟到了。

情况 4：今天截止 0 次缺席，今天截止 2 次连续迟到：

dp[i][0][2] = dp[i - 1][0][1];

过去 0 次缺席，昨天迟到，今天迟到了，（只能从 1 转来）。

情况 5：今天截止 1 次缺席，今天截止 1 次连续迟到：

dp[i][1][1] = dp[i - 1][1][0];

过去 1 次缺席，过去 0 次迟到，今天迟到了。

这里可以仔细想一下，我今天必须要迟到，所以今天截止的 1 次缺席必定来自过去。

情况 6：今天截止 1 次缺席，今天截止 2 次连续迟到：

dp[i][1][2] = dp[i - 1][1][1];

过去 1 次缺席，昨天迟到，今天迟到了。

最后，把最后一天的六种情况加和即为答案。

class Solution {public int checkRecord(int n) {final int MOD = 1000000007;int[][][] dp = new int[n + 1][2][3]; // 长度，A （缺席）的数量，结尾连续 L （迟到）的数量dp[0][0][0] = 1;for (int i = 1; i <= n; i++) {// 以 P 结尾的数量for (int j = 0; j <= 1; j++) {for (int k = 0; k <= 2; k++) {dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % MOD;}}// 以 A 结尾的数量for (int k = 0; k <= 2; k++) {dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % MOD;}// 以 L 结尾的数量for (int j = 0; j <= 1; j++) {for (int k = 1; k <= 2; k++) {dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % MOD;}}}int sum = 0;for (int j = 0; j <= 1; j++) {for (int k = 0; k <= 2; k++) {sum = (sum + dp[n][j][k]) % MOD;}}return sum;}
}

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。

上期推文：

LeetCode1-540题汇总，希望对你有点帮助！

LeetCode刷题实战541：反转字符串 II

LeetCode刷题实战542：01 矩阵

LeetCode刷题实战543：二叉树的直径

LeetCode刷题实战544：输出比赛匹配对

LeetCode刷题实战545：二叉树的边界

LeetCode刷题实战546：移除盒子

LeetCode刷题实战547：省份数量

LeetCode刷题实战548：将数组分割成和相等的子数组

LeetCode刷题实战549：二叉树中最长的连续序列