552. 学生出勤记录 II [hard]

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

给定一个正整数 n，返回长度为 n 的所有可被视为可奖励的出勤记录的数量。答案可能非常大，你只需返回结果mod 109 + 7的值。

学生出勤记录是只包含以下三个字符的字符串：

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

如果记录不包含多于一个'A'（缺勤）或超过两个连续的'L'（迟到），则该记录被视为可奖励的。

示例 1:

输入: n = 2
输出: 8 
解释：
有8个长度为2的记录将被视为可奖励：
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
只有"AA"不会被视为可奖励，因为缺勤次数超过一次。

注意：n 的值不会超过100000。

通过次数2,545 | 提交次数6,272

Second Try

2020-06-14

还是得靠题解才得到思路，先考虑LP，然后考虑A, A的引入真是很难想到。

class Solution(object):
    def checkRecord(self, n):
        """
        :type n: int
        :rtype: int

        仅考虑第N位为L和P。
        - 只要DP[n-1]符合要求，DP[n-1] + p 总归符合要求。
        - 考虑L, DP[n-1] + L仅在前两个已经是L的时候不符合要求，也即n-2和n-1为L, 顺带的要求 n-3必须为P， 否则DP[n-1]早已凑成3个L.
        不符合要求的序列版本只有一项排列，n-3到n位为PLLL，而n-4位置L/P皆可，因此出现PLLL的概率是DP[n-4].
        故符合要求的为: DP[n-1] + DP[n-1] - DP[n-4] = 2 * DP[n-1] - DP[n-4]
        
        这时候开始考虑A的位置，如果A不存在，则概率依然为DP[n]
        如果A存在，考虑A在位置i(i = 1...n), 左右位置的组合可能性分别为DP[i-1]和DP[n - i], 总可能性为二者笛卡尔积即可
        靠自己真是想不出来，还是得靠题解
        """
        if n == 0:
            return 1
        if n == 1:
            return 3
        if n == 2:
            return 8
        rem = 10 ** 9 + 7      
        DP = [0 for i in range(n + 1)]
        DP[0] = 1  # 这一步选择0还是1，也是挺容易出错的
        DP[1] = 2
        DP[2] = 4
        DP[3] = 7
        for i in range(4, n + 1):
            DP[i] = 2 * DP[i - 1] - DP[i - 4]
            DP[i] = DP[i] % rem
        rv = DP[n]
        for i in range(1, n + 1):
            rv += DP[i - 1] * DP[n - i]
            rv = rv % rem
        return rv 

执行用时 :528 ms, 在所有 Python 提交中击败了83.33%的用户
内存消耗 :19.6 MB, 在所有 Python 提交中击败了100.00%的用户

bug version

需要把DP[0, 1, 2, 3]都提前设置才行，在DP[i-4]不存在的时候不能直接当作0
在n=0,1,2的时候需要提前返回，不然DP[n]在初始赋(0,1,2, 3)的时候会超出边界。

# bug version
class Solution(object):
    def checkRecord(self, n):
        """
        :type n: int
        :rtype: int

        仅考虑第N位为L和P。
        - 只要DP[n-1]符合要求，DP[n-1] + p 总归符合要求。
        - 考虑L, DP[n-1] + L仅在前两个已经是L的时候不符合要求，也即n-2和n-1为L, 顺带的要求 n-3必须为P， 否则DP[n-1]早已凑成3个L.
        不符合要求的序列版本只有一项排列，n-3到n位为PLLL，而n-4位置L/P皆可，因此出现PLLL的概率是DP[n-4].
        故符合要求的为: DP[n-1] + DP[n-1] - DP[n-4] = 2 * DP[n-1] - DP[n-4]
        
        这时候开始考虑A的位置，如果A不存在，则概率依然为DP[n]
        如果A存在，考虑A在位置i(i = 1...n), 左右位置的组合可能性分别为DP[i-1]和DP[n - i], 总可能性为二者笛卡尔积即可
        靠自己真是想不出来，还是得靠题解
        """
        rem = 10 ** 9 + 7      
        DP = [0 for i in range(n + 1)]
        DP[0] = 1  # 这一步选择0还是1，也是挺容易出错的
        for i in range(1, n + 1):
            DP[i] = 2 * DP[i - 1] - DP[i - 4] if i >= 4 else 2 * DP[i - 1]
            DP[i] = DP[i] % rem
        rv = DP[n]
        for i in range(1, n + 1):
            rv += DP[i - 1] * DP[n - i]
            rv = rv % rem
        return rv 

First Try

2020-06-14

使用类似状态机的版本，非常直观容易理解

# 优化初始化版本，从第2级算起，总归比从第3级开始算起更不容易出bug
class Solution(object):
    def checkRecord(self, n):
        """
        :type n: int
        :rtype: int

        数学法:
        包含1个A的情况： C1-n * 2 ^ (n-1)
        包含0个A的情况: 2 ^ (n)， 直接指数爆炸了
        包含1个A的情况中，最多大于两个L的情况，算不出来了。。

        考虑状态机表示法，由于不能有连续三个L，也不能有两个A，因此只需要考虑6种可以继续的情况即可:
        (0L, 1L, 2L)和(0A, 1A)的笛卡尔积. L只考虑在最后1/2位的情况，并不考虑前3位的情况。
        """
        if n == 0:
            return 1
        if n == 1:
            return 3
        if n == 2:
            return 8
        # 开始三个字符的情况,总共27种情况，不允许的有8种（3L, 3A, 2A = 1 + 1 + 6 = 8)，剩下19种
        cache = {"A0L0": 2,  # 最后一位是P，前面两位可以是P/L的组合，总共4种
                "A0L1": 1,   # 最后一位是L，中间是P, 第一位可以是L/P
                "A0L2": 1, 
                "A1L0": 3,   # 最后一位不是L, 枚举A在3个位置的组合：A在第1位，则有两种选择，blabla
                "A1L1": 1, 
                "A1L2": 0}
        # 每一轮加法，L都可以被抹除掉，不过A只要出现过一次就一直都在，幸好A一直都在减轻了计算
        mod = 10 ** 9 + 7
        for i in range(3, n+1):
            next_cache = {}
            next_cache["A0L0"] = (cache["A0L0"] + cache["A0L1"] + cache["A0L2"]) % mod
            next_cache["A0L1"] = cache["A0L0"]
            next_cache["A0L2"] = cache["A0L1"]
            next_cache["A1L0"] = (cache["A1L0"] + cache["A1L1"] + cache["A1L2"] + cache["A0L0"] + cache["A0L1"] + cache["A0L2"]) % mod
            next_cache["A1L1"] = cache["A1L0"]
            next_cache["A1L2"] = cache["A1L1"]
            cache = next_cache
        return sum(cache.values()) % mod

执行用时 :1168 ms, 在所有 Python 提交中击败了27.78%的用户
内存消耗 :15.5 MB, 在所有 Python 提交中击败了100.00%的用户

bug version

仍然犯了之前棋盘问题中两个迭代矩阵之间互相影响的错误，当前轮次某个属性的状态被更新后，其状态仍然会用于更新其他属性，导致出现了在不同轮次之间的多重混淆。解决方法是每一轮都额外创建一个全新的列表用来保存下一轮的状态。

# 混淆版本, bug version
class Solution(object):
    def checkRecord(self, n):
        """
        :type n: int
        :rtype: int

        数学法:
        包含1个A的情况： C1-n * 2 ^ (n-1)
        包含0个A的情况: 2 ^ (n)， 直接指数爆炸了
        包含1个A的情况中，最多大于两个L的情况，算不出来了。。

        考虑状态机表示法，由于不能有连续三个L，也不能有两个A，因此只需要考虑6种可以继续的情况即可:
        (0L, 1L, 2L)和(0A, 1A)的笛卡尔积. L只考虑在最后1/2位的情况，并不考虑前3位的情况。
        """
        if n == 0:
            return 1
        if n == 1:
            return 3
        if n == 2:
            return 8
        # 开始三个字符的情况,总共27种情况，不允许的有8种（3L, 3A, 2A = 1 + 1 + 6 = 8)，剩下19种
        cache = {"A0L0": 4,  # 最后一位是P，前面两位可以是P/L的组合，总共4种
                "A0L1": 2,   # 最后一位是L，中间是P, 第一位可以是L/P
                "A0L2": 1, 
                "A1L0": 8,   # 最后一位不是L, 枚举A在3个位置的组合：A在第1位，则有两种选择，blabla
                "A1L1": 3, 
                "A1L2": 1}
        # 每一轮加法，L都可以被抹除掉，不过A只要出现过一次就一直都在，幸好A一直都在减轻了计算
        mod = 10 ** 9 + 7
        for i in range(4, n+1):
            cache["A0L0"] = (cache["A0L0"] + cache["A0L1"] + cache["A0L2"]) % mod
            cache["A0L1"] = (cache["A0L0"]) 
            cache["A0L2"] = cache["A0L1"]
            cache["A1L0"] = (cache["A1L0"] + cache["A1L1"] + cache["A1L2"] + cache["A0L0"] + cache["A0L1"] + cache["A0L2"]) % mod
            cache["A1L1"] = cache["A1L0"]
            cache["A1L2"] = cache["A1L1"]
        return sum(cache.values()) % mod

552. 学生出勤记录 II [hard]​

Second Try​

First Try​

552. 学生出勤记录 II [hard]

Second Try

First Try