This is the 17th day of my participation in the August Challenge

551. Student attendance Record I

You are given the string S to represent a student’s attendance record, each character of which is used to mark the day’s attendance (absence, lateness, presence). The record contains only the following three types of characters:

  • 'A'A) Absent B) Absent
  • 'L'Be Late be Late
  • 'P'Present, Present

A student can receive an attendance award if he/she meets both of the following criteria:

  • According to theTotal attendanceStudent absenteeism ('A')strictLess than two days.
  • studentsDon’tThere arecontinuousLateness of 3 days or more ('L') record.

Return true if the student can earn an attendance award; Otherwise, return false.

Example 1:

Input: s = "PPALLP" Output: true Explanation: Students are absent from school less than 2 times, and there is no record of continuous tardiness of 3 days or more.Copy the code

Example 2:

Input: s = "PPALLL" Output: falseCopy the code

Tip:

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

Methods a

Simulation: Iterate over the string and record the number of absences and the number of consecutive lateness. If the number of absences is greater than or equal to 2, or the number of consecutive lateness is 3 days, it does not match and returns 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; }}Copy the code

Time complexity: O(n)

Space complexity: O(1)

552. Student Attendance Record II

A student’s attendance record can be represented as a string, with each character marking the day’s attendance (absence, lateness, presence). The record contains only the following three types of characters:

  • 'A'A) Absent B) Absent
  • 'L'Be Late be Late
  • 'P'Present, Present

A student can receive an attendance award if he/she meets both of the following criteria:

  • According to theTotal attendanceStudent absenteeism ('A')strictLess than two days.
  • studentsDon’tThere arecontinuousLateness of 3 days or more ('L') record.

You are given an integer n that represents the length of the attendance record (number of times). Return the number of records in which an attendance reward is possible if the record length is N. The answer may be large, so return mod 109 + 7.

Example 1:

Input: n = 2 Output: 8 Explanation: There are eight records of length 2 that will be considered rewarding: "PP", "AP", "PA", "LP", "PL", "AL", "LA", "LL" Only "AA" will not be considered as rewarding as the number of absences is 2 (less than 2 are required).Copy the code

Example 2:

Input: n = 1 Output: 3Copy the code

Example 3:

Input: n = 10101 Output: 183236316Copy the code

Tip:

  • 1 <= n <= 10^5

Methods a

Dynamic programming:

Strings that can be rewarded for attendance meet two conditions:

  • AThe number of PI is less than 2
  • continuousLThe number of PI is less than 3

State definition: f[I][j][k] is expressed as length I, where the number of A is J, and the number of continuous L ending with I is K;

State transfer: according to the conventional analysis of the last element, which states can be transferred from the length of I and the last two dimensions of J and K, we need to enumerate not only the state of length I, but also the state of length I-1, which is complicated; F [I][j][k] can be transferred from the current f[I][j][k] to the states of length I +1;

  • i+1This is A,j + 1 < 2.f[i+1][j+1][0] += f[i][j][k]
  • i+1L in the place,k + 1 < 3.f[i+1][j][k+1] += f[i][j][k]
  • i+1I have P in place,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; }}Copy the code