Java实现 LeetCode 552 学生出勤记录 II（数学转换？还是动态规划？）

552. 学生出勤记录 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。

先附上大佬用数学方法做的：

用数组放入关系，太顶了

下面才是我写的勉强过关的代码

class Solution {

   public int checkRecord(int n) {

		long[][] a = new long[][]{{1},{1},{0},{1},{0},{0}};

		long[][] aMatrix = new long[][]{{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}};

		while (n>0) {

			int m = n & 1;

			if (m == 1) {

				a = this.multipleMatrix(aMatrix, a);

			}

			aMatrix = this.multipleMatrix(aMatrix, aMatrix);

			n = n>>1;

		}

		/**

		* 0 A0L0

		* 1 A0L1

		* 2 A0L2

		* 3 A1L0

		* 4 A1L1

		* 5 A1L2

		*/

		return (int)a[3][0];

	}

	public long[][] multipleMatrix(long[][] a,long[][] b) {

		long mod = (long)1e9+7;

		long c[][] = new long[a.length][b[0].length];

		for (int i = 0; i < a.length; i++) {

			for (int j = 0; j < b[i].length; j++) {

				for (int k = 0; k < a[i].length; k++) {

					c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;

				}

			}

		}

		return c;

	}

}

class Solution {

    long M = 1000000007;

    public int checkRecord(int n) {

        long[] f = new long[n <= 5 ? 6 : n + 1];

        f[0] = 1;

        f[1] = 2;

        f[2] = 4;

        f[3] = 7;

        //四种情况下，我前三个可奖励，我最后一个是l是p无所谓

        //如果中间出现两个LL，那么我必定无效

        //2*f[i-1]和一个-f[i-4]

        for (int i = 4; i <= n; i++)

            f[i] = ((2 * f[i - 1]) % M + (M - f[i - 4])) % M;

        long sum = f[n];

        for (int i = 1; i <= n; i++) {

            sum += (f[i - 1] * f[n - i]) % M;

        }

        return (int)(sum % M);

    }

}

巴特西

Java实现 LeetCode 552 学生出勤记录 II（数学转换？还是动态规划？）

552. 学生出勤记录 II

最新文章

热门文章