LeetCode每日一题 551 552 . 学生出勤记录 I II

这是我参与8月更文挑战的第17天，活动详情查看：8月更文挑战

551. 学生出勤记录 I

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

• 'A'：Absent，缺勤

• 'L'：Late，迟到
• 'P'：Present，到场

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

• 按 总出勤 计，学生缺勤（'A'）严格 少于两天。
• 学生 不会 存在 连续 3 天或 3 天以上的迟到（'L'）记录。

如果学生可以获得出勤奖励，返回 true ；否则，返回 false 。

示例 1：

输入：s = "PPALLP"
输出：true
解释：学生缺勤次数少于 2 次，且不存在 3 天或以上的连续迟到记录。
复制代码

示例 2：

输入：s = "PPALLL"
输出：false
解释：学生最后三天连续迟到，所以不满足出勤奖励的条件。
复制代码

提示：

• 1 <= s.length <= 1000
• s[i] 为 'A'、'L' 或 'P'

方法一

模拟：遍历一遍字符串，记录缺勤的次数和连续迟到的次数，若缺勤次数大于等于2，或者连续迟到3天，则不符合，返回false

class Solution {
    public boolean checkRecord(String s) {
        int a = 0;
        for (int i = 0, j = 0; i < s.length(); i ++ ) {
            char c = s.charAt(i);
            if (c == 'A') {
                a ++;
                j = 0;
            }
            else if (c == 'L') j ++;
            else j = 0;
            if (j >= 3) return false;
            if (a >= 2) return false;
        }
        return true;
    }
}
复制代码

时间复杂度： O(n)

空间复杂度： O(1)

552. 学生出勤记录 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 <= 10^5

方法一

动态规划：

可以获得出勤奖励的字符串都符合下面两个条件：

• A的个数小于2
• 连续L的个数小于3

状态定义：f[i][j][k]表示为长度为i，其中A的个数为j，且以i为结尾的连续L的个数为k；

状态转移：若以常规的按最后一个元素来分析，长度为i且后两维为j和k可以由哪些状态转移过来，我们不仅要枚举长度为i的状态，还要枚举长度为i-1的状态，比较复杂；此题，可以换个思路，我们从当前这个f[i][j][k]可以转移到长度为i+1的哪些状态；

• i+1位上是A，j + 1 < 2，f[i+1][j+1][0] += f[i][j][k]
• i+1位上是L，k + 1 < 3，f[i+1][j][k+1] += f[i][j][k]
• i+1位上是P，f[i+1][j][0] += f[i][j][k]

class Solution {
    public int checkRecord(int n) {
        int[][][] f = new int [n + 1][2][3];
        f[0][0][0] = 1;
        int mod = 1000000007;
        for (int i = 0; i < n; i ++ ) 
            for (int j = 0; j < 2; j ++ )
                for (int k = 0; k < 3; k ++ ) {
                    f[i + 1][j][0] = (f[i + 1][j][0] + f[i][j][k]) % mod;
                    if (j + 1 < 2) f[i + 1][j + 1][0] = (f[i + 1][j + 1][0] + f[i][j][k]) % mod;
                    if (k + 1 < 3) f[i + 1][j][k + 1] = (f[i + 1][j][k + 1] + f[i][j][k]) % mod;
                }
        int res = 0;
        for (int i = 0; i < 2; i ++ )
            for (int j = 0; j < 3; j ++ )
                res = (res + f[n][i][j]) % mod;
        return res;
    }
}
复制代码