This is the 17th day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Leetcode -551- Student attendance record

[Blog link]

The way to study 🐔

The nuggets home page

[Topic description]

You are given a string s representing a student’s attendance record, where each character marks the day’s attendance (absence, tardiness, attendance). Records contain only the following three types of characters:

• A. Absent B. Absent C. Absent
• ‘L’ : Late
• ‘P’ : Present

Students can receive an attendance reward if they can meet both of the following conditions:

A student’s absence (‘A’) is strictly less than two days in total attendance. Students will not have a record of being late (‘L’) for 3 consecutive days or more.

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

Example 1:

Input: s = "PPALLP" Output: trueCopy the code

Example 2:

Input: s = "PPALLL" Output: false Explanation: The student is late for the last three days in a row, so the condition of attendance reward is not met.Copy the code

Tip:

• 1 <= s.length <= 1000
• S [I] = ‘A’, ‘L’ or ‘P’

Related Topics

• string
• 👍 👎 0 81

[Topic link]

Leetcode title link

[making address]

Code link

[思路介绍]

Idea 1: Java native functions

• Conditional judgment

 public boolean checkRecord(String s) {
     return! (s.indexOf("A") != s.lastIndexOf("A") || s.contains("LLL"))}Copy the code

• Time complexity O(
  $n$)
• Space complexity O(1)

---

Thinking extension

• Make a prediction for tomorrow’s daily question

The title description can represent a student’s attendance record as a string, with each character marking the day’s attendance (absence, tardiness, attendance). Records contain only the following three types of characters:

• A. Absent B. Absent C. Absent
• ‘L’ : Late
• ‘P’ : Present

Students can receive an attendance reward if they can meet both of the following conditions:

A student’s absence (‘A’) is strictly less than two days in total attendance. Students will not have a record of being late (‘L’) for 3 consecutive days or more.

You are given an integer n, which represents the length (number) of attendance records. Please return the number of records in which an attendance reward is possible for a record length of N. The answer could be large, so return the mod of 109 + 7.

Example 1:

Input: n = 2 Output: 8 Description: There are eight types of records of length 2 that will be considered rewarding: "PP", "AP", "PA", "LP", "PL", "AL", "LA", "LL" only "AA" will not be considered rewarding because the number of absences is 2 (less than 2 is 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 <= 105

Related Topics

• Dynamic programming
• 👍 👎 0 144
• This hunch is a daily question for tomorrow
• Easy to hard is also ruthless, first write a regular DP analysis
• The normal recursion is to choose one out of three DFS (I) for each element.
• Baseline conditions: I reaches n | | current arrangement does not satisfy the topic request when out of recursion
• The time complexity O(3n)O(3^n)O(3n) makes it easy to find tle
• But from this we can derive the dp equation DP [I]
• Represents the number of schemes arranged and combined by I elements to meet the requirements of the problem
• Initialize dp[0] = 0;
• Dp [n] recursion idea can be analyzed from the following perspective
  • The principle of choosing the NTH element is that you need to make sure that the permutation is satisfactory
  • Divide namely the following several cases
    • If the current order scheme DP [n-1] has A, only P and L can be added.
    • If the end of dp[n-1] is “LL”, only P can be added
    • In other cases, all elements A, L, and P can be added
  • From this we can see that we need two indicators to record the number of each scheme
    • 1. The number of A
    • 2, the end of the two-digit string
  • So one-dimensional DP [n] doesn’t satisfy the definition for the time being
• It is necessary to define 3d DP [I][j][k] to represent using I elementsJ A,And the end of the length isK lNumber of schemes
  • Initialize the
    • dp[1][0][1] = 1
    • dp[1][1][0] = 1
    • dp[1][0][0] = 1
  • Recursive equation
    • dp[i][0][0] = (dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2]) % mod;
    • dp[i][1][0] = (dp[i-1][1][0] + dp[i-1][1][1] + dp[i-1][1][2]) % mod;
    • dp[i][0][1] = (dp[i-1][0][0]) % mod;
    • dp[i][0][2] = (dp[i-1][0][1]) % mod;
    • dp[i][1][1] = (dp[i-1][1][0]) % mod;
    • dp[i][1][2] = (dp[i-1][1][1]) % mod;
    • dp[i][1][0] += (dp[i – 1][0][0] + dp[i – 1][0][1] + dp[i – 1][0][2]) % mod

public int checkRecord(int n) {
    long[][][] dp = new long[n + 1] [2] [3];
    dp[1] [0] [1] = 1;
    dp[1] [1] [0] = 1;
    dp[1] [0] [0] = 1;
    int mod = (int) 1e9 + 7;
    for (int i = 2; i <= n; i++) {
        dp[i][0] [0] = (dp[i - 1] [0] [0] + dp[i - 1] [0] [1] + dp[i - 1] [0] [2]) % mod;
        dp[i][1] [0] = (dp[i - 1] [1] [0] + dp[i - 1] [1] [1] + dp[i - 1] [1] [2]) % mod;
        dp[i][0] [1] = dp[i - 1] [0] [0];
        dp[i][0] [2] = dp[i - 1] [0] [1];
        dp[i][1] [1] = dp[i - 1] [1] [0];
        dp[i][1] [2] = dp[i - 1] [1] [1];
        dp[i][1] [0] += (dp[i - 1] [0] [0] + dp[i - 1] [0] [1] + dp[i - 1] [0] [2]) % mod;
    }
    return (int)((dp[n][0] [0] + dp[n][0] [1] + dp[n][0] [2] + dp[n][1] [0] + dp[n][1] [1] + dp[n][1] [2]) % mod);
}
Copy the code

• Time complexity O(n)
• Space complexity O(n)