Easy

题目描述

给你一个字符串 s 表示一个学生的出勤记录，其中的每个字符用来标识学生在某一天的出勤情况。记录仅包含以下三个字符：

  • 'A'：缺勤
  • 'L'：迟到
  • 'P'：到场

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

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

如果学生可以获得出勤奖励，返回 true；否则，返回 false。

示例 1：

输入：s = "PPALLP"
输出：true
解释：学生缺勤次数少于 2 次，且不存在 3 天或以上的连续迟到记录。

示例 2：

输入：s = "PPALLL"
输出：false
解释：学生最后 3 天连续迟到，所以不满足出勤奖励的条件。

提示：

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

解题思路

解题思路

这道题需要检查两个条件：

  1. 缺勤（‘A’）总数少于 2 天
  2. 没有连续 3 天或以上的迟到（‘L’）

方法一：一次遍历（推荐）

  • 维护缺勤计数器和连续迟到计数器
  • 遍历字符串，遇到 ‘A’ 时增加缺勤计数，如果超过 1 则直接返回 false
  • 遇到 ‘L’ 时增加连续迟到计数，如果达到 3 则直接返回 false
  • 遇到其他字符时重置连续迟到计数器

方法二：字符串查找

  • 使用字符串的 count/indexOf 等方法直接查找
  • 检查 ‘A’ 的总数和是否包含 “LLL” 子串

方法一更高效，因为可以提前终止，而且逻辑更清晰。时间复杂度都是 O(n)，但方法一的常数因子更小。

代码实现

class Solution {
public:
    bool checkRecord(string s) {
        int absent = 0;
        int consecutive_late = 0;
        
        for (char c : s) {
            if (c == 'A') {
                absent++;
                if (absent >= 2) return false;
                consecutive_late = 0;
            } else if (c == 'L') {
                consecutive_late++;
                if (consecutive_late >= 3) return false;
            } else {
                consecutive_late = 0;
            }
        }
        
        return true;
    }
};

class Solution:
    def checkRecord(self, s: str) -> bool:
        absent = 0
        consecutive_late = 0
        
        for c in s:
            if c == 'A':
                absent += 1
                if absent >= 2:
                    return False
                consecutive_late = 0
            elif c == 'L':
                consecutive_late += 1
                if consecutive_late >= 3:
                    return False
            else:
                consecutive_late = 0
        
        return True

public class Solution {
    public bool CheckRecord(string s) {
        int absent = 0;
        int consecutiveLate = 0;
        
        foreach (char c in s) {
            if (c == 'A') {
                absent++;
                if (absent >= 2) return false;
                consecutiveLate = 0;
            } else if (c == 'L') {
                consecutiveLate++;
                if (consecutiveLate >= 3) return false;
            } else {
                consecutiveLate = 0;
            }
        }
        
        return true;
    }
}

var checkRecord = function(s) {
    let absentCount = 0;
    let consecutiveLate = 0;
    
    for (let i = 0; i < s.length; i++) {
        if (s[i] === 'A') {
            absentCount++;
            if (absentCount >= 2) return false;
            consecutiveLate = 0;
        } else if (s[i] === 'L') {
            consecutiveLate++;
            if (consecutiveLate >= 3) return false;
        } else {
            consecutiveLate = 0;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次，n 为字符串长度
空间复杂度O(1)只使用常数个额外变量

相关题目