题目解析
* 输入输出:输入为一行字符串,包含若干待检测密码,各密码间以英文逗号 , 分隔(单个密码内部不含空格和逗号)。需按输入顺序,每行输出一组合规的密码;不合规的密码不输出。
* 数据范围:输入总行长不超过 100100100,单密码长度在题目要求外无其他限制(但代码中通过长度检查过滤)。
* 复杂度要求:字符串长度极小,O(L)O(L)O(L)(LLL 为输入总长)的线性扫描即可满足 1s1\text{s}1s 时限。
* 算法知识点:字符串处理、模拟验证、字符串分割、字符分类统计
思路解析
1. 字符串分割:由于输入将多个密码用逗号连接成一行,需将其拆分为独立密码串处理。利用 string::find(',') 定位分隔符,提取子串后,使用 erase 删除已处理部分(包括逗号),循环直至字符串为空。
2. 多条件验证(check函数):
* 长度筛选:首先检查长度是否在 [6,12][6, 12][6,12] 区间内,不满足直接返回 false。
* 字符集过滤:遍历密码每个字符,若出现非大小写字母、非数字、且非 !@#$ 的字符,立即判定不合规。
* 类型统计:维护四个计数器:
* upper_cnt:大写字母是否存在(标记型,最多为1)
* lower_cnt:小写字母是否存在(标记型,最多为1)
* number_cnt:数字是否存在(标记型,最多为1)
* special_cnt:特殊字符 !@#$ 的累计数量(题目要求至少1个)
* 组合条件判定:检查 (upper_cnt + lower_cnt + number_cnt) >= 2(字母数字类至少两种)且 special_cnt > 0(至少一个特殊字符),均满足返回 true。
3. 输出控制:主循环中,仅当 check(temp) 返回真时,输出该密码子串。
完整代码