🎈 作者：Linux猿
🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我，关注我，有问题私聊！
🎈 关注专栏： 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀
🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬
目录
一、题目描述
密码要求：
1.长度超过8位；
2.包括大小写字母.数字.其它符号,以上四种至少三种；
3.不能有相同长度大于2的子串重复；
1.2 输入描述
一组或多组长度超过2的子符串。每组占一行
1.3 输出描述
如果符合要求输出：OK，否则输出NG
二、解题思路
本题是一道模拟题，按照密码要求一次检查即可。
（1）条件 1：如果字符串长度小于等于 8 位，则不符合要求；
（2）条件 2：计算有多少种字符，少于三种则不符合要求，可以使用数组计数或者位运算计数；
（3）条件 3：只需要判断长度为 3 的子串是否有重复即可，这个可通过两层 for 循环或者 find 函数来实现。
三、代码实现
代码实现如下所示。
-
#include <iostream>
-
#include <string>
-
using
namespace std;
-
-
bool checkPasswd(string str)
-
{
-
// 条件 1
-
if (str.
size() <=
8) {
-
return
false;
-
}
-
-
// 条件 2
-
int n = str.
size();
-
int num =
0;
-
for (
int i =
0; i < n; ++i) {
-
if (
isupper(str[i])) {
-
num |=
1;
-
}
else
if (
islower(str[i])) {
-
num |=
2;
-
}
else
if (str[i] >=
'0' && str[i] <=
'9') {
-
num |=
4;
-
}
else {
-
num |=
8;
-
}
-
}
-
-
int m =
0;
-
int p =
1;
-
for (
int i =
0; i <
4; ++i) {
-
if (num & p) {
-
m++;
-
}
-
p = p *
2;
-
}
-
if (m <
3)
return
false;
-
-
// 条件 3
-
for (
int i =
0; i < n -
2; ++i) {
-
int idx = str.
find(str.
substr(i,
3),
0);
-
int idy = str.
find(str.
substr(i,
3), idx +
1);
-
if (idy !=
-1) {
-
return
false;
-
}
-
}
-
return
true;
-
}
-
-
int main()
-
{
-
string str;
-
while (
getline(cin, str)) {
-
bool flag =
checkPasswd(str);
-
if (flag) {
-
cout<<
"OK"<<endl;
-
}
else {
-
cout<<
"NG"<<endl;
-
}
-
}
-
return
0;
-
}
四、时间复杂度
时间复杂度：O(n + 3n^2)。
在上述代码中，假设字符串长度为 n，第一个 for 循环遍历字符种类的时间复杂度为 O(n)，计算是否存在子串的时间复杂度为 O(3n^2)，所以总的时间复杂度为 O(n + 3n^2)。
🎈 感觉有帮助记得「一键三连」支持下哦！有问题可在评论区留言💬，感谢大家的一路支持！🤞猿哥将持续输出「优质文章」回馈大家！🤞🌹🌹🌹🌹🌹🌹🤞
转载：https://blog.csdn.net/u011074149/article/details/127819420
查看评论