一、问题重述
- 需要做的操作：
- 字数限制：少于6个时优先插入，多于20个时优先删除
- 种类限制：种类不足3种（小写字母、大写字母、数字）时，优先插入或替换
- 重复限制：不得连续重复超过3次
- 分析：
- 出现连续的长字符串(
长度l>=3)时：- 若超出长度大于总超出长度，优先删除至等长，再进行替换。优先删除较短的长字符串（长度为
k需要k-2次删除，或(k-2)/3次替换） - 若总长度未超，优先替换
- 若总长度不足，优先插入，替换次之
- 若超出长度大于总超出长度，优先删除至等长，再进行替换。优先删除较短的长字符串（长度为
- 出现种类不足时：
- 若总长度不足，优先插入，替换次之
- 若总长度未超，优先替换
- 若总长度超出，优先删除长度大于3的较短字符串，并尽量保留种类，再替换
- 仅剩长度异常时：
- 长度不足时，优先插入
- 长度超出时，优先删除
- 出现连续的长字符串(
-
案例：
string num [insert, replace, ,delete] “ABABABABABABABABABAB1” 2 [0,1,1] “aaaaa” 2 [1,1,0] “1010101010aaaB10101010” 2 [0,0,2]
二、C++ AC代码
struct Comp {
bool operator () (const int &x, const int &y) const {
return x % 3 > y % 3;
}
};
class Solution {
public:
int strongPasswordChecker(string s) {
priority_queue<int, vector<int>, Comp> pq;
int ans=0, flag=111, size=s.length();
int numi= size<6 ? 6-size : 0; // at least insert: numi
int numd= size>20? size-20: 0; // at least delete: numd
int i=-1, j=0;
// cal type number
while(++i<size){
if(flag){
if(flag-99>0 && s[i]<='z' && s[i]>='a') flag -= 100;
if(flag%100>9 && s[i]<='Z' && s[i]>='A') flag -= 10;
if(flag%10>0 && s[i]<='9' && s[i]>='0') flag -= 1;
}
}
int numf = (flag>99) + (flag%100>9) + (flag%10>0);
// cal repeatment
i=0, j=1;
while(i<size){
while(j<size && s[i]==s[j]) ++j;
if(j-i>2) pq.push(j-i);
i=j++;
}
// delete
while(numd && !pq.empty()){
i = pq.top(); pq.pop();
if (i-1>=3) pq.push(i-1);
numd--, ans++;
}
// insert
while(numi && !pq.empty()){
i = pq.top(); pq.pop();
if (i-2>=3) pq.push(i-2);
numi--, ans++, numf--;
}
// replace
while(!pq.empty()){
i = pq.top(); pq.pop();
ans += i/3, numf -= i/3;
}
numf = numf < 0 ? 0 : numf;
numi = numi-numf>0 ? numi-numf : 0;
return ans+numi+numf+numd;
}
};