0552：学生出勤记录 II（★★）

Ian

2016-07-05 约 579 字预计阅读 2 分钟次阅读

力扣第 552 题

题目

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

'A'：Absent，缺勤
'L'：Late，迟到
'P'：Present，到场

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

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

给你一个整数 n ，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况数量。答案可能很大，所以返回对 10⁹ + 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⁵

相似问题：

0551：学生出勤记录 I

分析

按最后一个字符递推
令 f[i][j][k] 代表长度 i，有 j 个 ‘A’ 且末尾 k 个连续 ‘L’ 的个数，即可递推
可以用滚动数组优化掉 i，还可以将 j 和 k 合并为一维

解答

1
2
3
4
5
6
7


class Solution:
    def checkRecord(self, n: int) -> int:
        mod = 10**9+7
        f = [1,0,0,0,0,0]
        for _ in range(n):
            f = [sum(f[:3])%mod,f[0],f[1],sum(f)%mod,f[3],f[4]]
        return sum(f)%mod

550 ms

*附加

这是完全的线性递推关系，还可以用矩阵快速幂优化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def checkRecord(self, n: int) -> int:
        def mpow(mat, n):
            res = mat
            for i in range(n.bit_length()-2,-1,-1):
                res = res*res%mod
                if n&1<<i:
                    res = res*mat%mod
            return res

        import numpy as np
        mod = 10**9+7
        A = np.asmatrix([[1,1,1,0,0,0],[1,0,0,0,0,0],[0,1,0,0,0,0],
                        [1,1,1,1,1,1],[0,0,0,1,0,0],[0,0,0,0,1,0]])
        f = np.asmatrix([[1],[0],[0],[0],[0],[0]])
        f = mpow(A,n)*f
        return int(np.sum(f)%mod)

86 ms

目录

0552：学生出勤记录 II（★★）

题目

分析

解答

*附加