文章目录
题目
标题和出处
标题：学生出勤记录 I
难度
2 级
题目描述
要求
给定一个字符串 s \texttt{s} s 来代表一个学生的出勤记录，每个字符表示这个学生当前是缺勤、迟到或到场。记录仅包含以下三个字符：
- ‘A’ \texttt{`A'} ‘A’：缺勤
- ‘L’ \texttt{`L'} ‘L’：迟到
- ‘P’ \texttt{`P'} ‘P’：到场
如果一个学生同时满足以下两个条件，则有资格获得出勤奖赏：
- 这个学生的缺勤（ ‘A’ \texttt{`A'} ‘A’）总数严格少于 2 \texttt{2} 2 天；
- 这个学生没有出现连续 3 \texttt{3} 3 天及以上的迟到（ ‘L’ \texttt{`L'} ‘L’）。
如果这个学生有资格获得出勤奖赏，返回 true \texttt{true} true，否则返回 false \texttt{false} false。
示例
示例 1：
输入：
s
=
"PPALLP"
\texttt{s = "PPALLP"}
s = "PPALLP"
输出：
true
\texttt{true}
true
解释：学生的缺勤数少于
2
\texttt{2}
2 个并且没有
3
\texttt{3}
3 个及以上的连续的迟到。
示例 2：
输入：
s
=
"PPALLL"
\texttt{s = "PPALLL"}
s = "PPALLL"
输出：
false
\texttt{false}
false
解释：学生在最后
3
\texttt{3}
3 天连续迟到，所以不满足出勤奖励的条件。
数据范围
- 1 ≤ s.length ≤ 1000 \texttt{1} \le \texttt{s.length} \le \texttt{1000} 1≤s.length≤1000
- s[i] \texttt{s[i]} s[i] 是 ‘A’ \texttt{`A'} ‘A’， ‘L’ \texttt{`L'} ‘L’ 或 ‘P’ \texttt{`P'} ‘P’
解法
思路和算法
如果一个学生有资格获得出勤奖赏，则需要同时满足两个条件，只需要分别检查这两个条件是否满足即可。
直观的解法是遍历字符串两次，第一次遍历检查缺勤总数是否满足条件，第二次遍历检查迟到情况是否满足条件。其实，可以在一次遍历中完成两个条件的检查。
一次遍历的做法是，维护两个变量分别记录缺勤总数和连续迟到天数，遍历过程中进行如下操作：
-
如果遇到 ‘L’ \text{`L'} ‘L’，则将连续迟到天数加 1 1 1，否则将连续迟到天数清零；
-
如果遇到 ‘A’ \text{`A'} ‘A’，则将缺勤总数加 1 1 1。
遍历过程中，只要出现缺勤总数达到 2 2 2 或者连续迟到天数达到 3 3 3，无论是否遍历结束，该学生已经失去获得出勤奖赏的资格，因此返回 false \text{false} false。
当遍历结束时，如果没有出现缺勤总数达到 2 2 2 或者连续迟到天数达到 3 3 3，则该学生有资格获得出勤奖赏，返回 true \text{true} true。
代码
class Solution {
public boolean checkRecord(String s) {
int absents = 0, continuousLates = 0;
int length = s.length();
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (c == 'L') {
continuousLates++;
} else {
if (c == 'A') {
absents++;
}
continuousLates = 0;
}
if (absents >= 2 || continuousLates >= 3) {
return false;
}
}
return true;
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是字符串 s s s 的长度。需要遍历字符串一次。
-
空间复杂度： O ( 1 ) O(1) O(1)。