我必须承认这道题目非常恶心,其被称为hard题并不在于他使用了什么特别难想到的方法,而是在于整个程序逻辑思路的整体,你需要考虑特别多的情况,并且按照处理流程整理出来。
我这里提出几个需要注意的点:
1:replace
操作永远都是最高效的操作,在字符长度符合要求的情况下,你可以只使用replace
而不必在考虑insertion
和deletetion
。
2:insertion
和deletion
是一对互斥操作,你不会既进行insertion
也进行deletion
。我们的操作就只有insertion + replace
或者 deletion + replace
。
3: 在delete时我们我们需要考虑如下情况,aaaaaa
进行一次del
然后再replace
,是最高效的,所以我们删除时还需要考虑当时连续字符的状态才可以。(处理这个问题我使用的是贪心算法)。
4:addtion
,replace
操作可以帮助我们补齐不够的类型。
class Solution {
public:
int strongPasswordChecker(string s) {
vector<int> nums(3, 0), series; // lowercase uppercase digit
int count{1}, typenum{0}, mininum{0};
vector<int> replref; // make replace reference
for(int i = 0; i < 21; i++)
replref.push_back(i / 3);
for(int i = 0; i < s.size(); i++){
if(s[i] >= 'A' && s[i]<= 'Z')
nums[0]++;
else if(s[i] >= 'a' && s[i] <= 'z')
nums[1]++;
else if(s[i] >= '0' && s[i] <= '9')
nums[2]++;
// series judge
if(i > 0 && s[i - 1] == s[i])
count++;
else{
if(count >= 3)
series.push_back(count);
count = 1;
}
}
if(count >= 3)
series.push_back(count);
for(auto n : nums)
typenum += (n == 0 ? 1 : 0);
// Insertion and deletion is mutually exclusive operation
if(s.size() > 20){
int delenum = s.size() - 20, i = 0;
// align series
for(int j = 0; j <= 1 && delenum > 0; j++){
for(int i = 0; i < series.size() && delenum > 0; i++){
if(series[i] % 3 == j){
if(delenum > j + 1){
series[i] -= j + 1;
delenum -= j + 1;
mininum += j + 1;
}else{
series[i] -= delenum;
mininum += delenum;
delenum = 0;
}
}
}
}
// 3 power delete
for(int i = 0; i < series.size() && delenum > 0; i++){
int del = min(delenum, (series[i] / 3) * 3);
series[i] -= del;
delenum -= del;
mininum += del;
}
for(int i = 0; i < series.size(); i++){
mininum += replref[series[i]];
typenum -= replref[series[i]];
}
mininum += delenum + max(typenum, 0);
}else if(s.size() < 6){
// addtion
int addnum = 6 - s.size(), i = 0;
for(; i < series.size(); i++){
int breneed = (series[i] + 1) / 2 - 1;
if(breneed <= addnum){
mininum += breneed;
addnum -= breneed;
typenum -= breneed;
}else{
mininum += addnum;
series[i] -= 2 * addnum;
typenum -= addnum;
addnum = 0;
break;
}
}
// replace
for(; i < series.size(); i++){
mininum += replref[series[i]];
typenum -= replref[series[i]];
}
mininum += max(addnum, typenum);
}else{
// only replace
for(int i = 0; i < series.size(); i++){
mininum += replref[series[i]];
typenum -= replref[series[i]];
}
mininum += max(typenum, 0);
}
return mininum;
}
};