P3255. 考勤信息

解题思路

每个人的考勤都是独立的，所以可以构建一个 `check()` 函数来判断每一个人的情况，记录某一个特定的人是否可以获得全勤奖。

`check()` 函数的构建包含如下步骤：

1. 判断是否存在 1 天以上的缺勤 2. 判断任意连续的 2 天，是否均为 迟到/早退 3. 判断任意连续的 7 天，是否存在 3 天以上的迟到/早退/缺勤

这三个只要有一个条件成立，直接返回 False，否则返回 True。

整体而言，题目难度并不高，只是需要对每一个条件进行较为细致的分类讨论和处理。

另外要注意取哈希表的 key 的时候，字符串单词一定不要拼错。

缺勤数量的判断

缺勤天数的判断非常好做，用哈希表计数器 `Counter()` 即可完成。

连续两天的判断

仅需遍历整个 lst 数组，考虑连续的两个元素 lst[i] 和 lst[i+1]，查看是否均为早退/迟到即可。

连续七天的判断

这是这道题里面稍微有点难度的地方，显然我们需要考虑所有的长度为 7 的连续区间，统计其中早退/迟到/缺席的天数的和是否超过 3。

很容易想到应该使用 固定滑窗 来实现。

构建一个新的哈希表 cnt_win，来表示窗口中各个元素出现的次数。

在滑窗过程中，仅需判断 cnt_win["leaveearly"] + cnt_win["late"] + cnt_win["absent"] 是否大于 3 即可。如果是，则可以直接返回 "false"。

如果嫌判断 cnt_win["leaveearly"] + cnt_win["late"] + cnt_win["absent"] > 3 的写法太麻烦，还可以换一个角度来写，考虑 正常上班的天数是否小于 4 天，即判断 cnt_win["present"] < 4，这样也可以大大缩短代码量。

PS：由于在 Python 的切片比较灵活，当某个人的考勤总天数不足 7 天时，cnt_win = Counter(lst[:7]) 并不会产生越界报错。

但对于使用其他语言的同学来说，是需要考虑越界的，可以将遍历的右边界从 7 改为取 7 和 n 之间的较小值，这样就不会出现越界操作。

当 n <= 7 时，也自然不会进入后续的固定滑窗过程了。

Java 代码为：

C++ 代码为：

复杂度分析 设 n 为人数，d 为某一个人考勤记录的天数（各人可以不同，先按单人分析 check 函数）。

• 单人 check 的时间复杂度：O(d)。函数内部是四段依次执行的线性工作：用 Counter 统计整份记录（拿到缺勤次数）遍历一次，O(d)；检查任意相邻两天是否连续迟到/早退，再遍历一次，O(d)；初始化前 7 天的窗口计数，O(7)；固定滑窗从第 7 天推进到末尾，每一步只做计数加一、减一和对 leaveearly/late/absent 三个键求和比较，均为 O(1)，合计 O(d)。四段相加仍是 O(d)，没有嵌套放大，瓶颈就是对这份记录的常数趟扫描。
• 总时间复杂度：对 n 个人逐一调用 check，为 O(所有人天数之和)，与输入总量成线性。
• 空间复杂度：单人 O(d)，主要是按空格切分出的考勤列表 lst；两个计数器 cnt 与 cnt_win 的键只有 absent、late、leaveearly、present 四种，属于常数级别开销。