题目链接：
https://leetcode.com/problems/strong-password-checker/
题意：
给定字符串，判断满足以下情况的最小操作数：
- 长度在$6到12$之间
- 至少包含一个小写字母，一个大写字母，一个数字。
- 不能包含连续三个一样的字符。
分析：
首先明确对于长度为$cnt$的连续相同字符，为了破坏，我们必须在某些位置上进行替换，共有$cnt/3$个这样的位置。
对于长度不足$20$的字符串，贪心的把删除和插入都使用替换即可。
对于长度不足$6$的字符串，注意插入字符串后长度依然小于$6$的情况。
对于长度大于$20$的字符串，我们不必在全部使用替换破坏后再删除，可以直接用删除操作进行破坏，若$mod\ 3=0$，可以删除最边上一组的一个字符，若$mod\ 3= 1$，可以删除最边上一组和剩下的$1$中的两个，若$mod \ 3=2$，则需删除三个。此时替换操作均减少一。
如果如上删除操作全部进行后长度依然大于$20$，那么可以将替换操作改为$3$个删除操作，这样比直接删除可以少一个操作。
最后注意模数越小，修改替换操作所需要的删除操作数越少。应该优先考虑。
代码：
写的很丑。。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
| class Solution { public: typedef pair<int, int>p; int strongPasswordChecker(string s) { int len = s.length(); priority_queue<p, vector<p>, greater<p> >q; if(len <= 3) return 6 - len; int lower = 0, upper = 0, digit = 0; int i = 0, j = 0; int add = 0, tot = 0; int bdel = 0; while(i < len){ while(s[i] == s[j] && j < len) j++; j--; if(j - i > 1){ int cnt = j - i + 1; q.push(p(cnt % 3, cnt / 3)); bdel += cnt / 3; } if(s[i] >= 'A' && s[i] <= 'Z') upper = 1; else if(s[i] >= 'a' && s[i] <= 'z') lower = 1; else if(s[i] >= '0' && s[i] <= '9') digit = 1; i = j + 1; j = i; } add = 3 - (digit + lower + upper); if(len >= 6 && len < 20){ if(add <= bdel){ tot = bdel; }else{ tot = add; } }else if(len > 20){ if(add < bdel){ int ctot = 0, dtot = 0; while(!q.empty()){ p tmp = q.top(); q.pop(); if(dtot >= len - 20){ ctot += tmp.second; }else{ ctot += tmp.second - 1; if(tmp.first == 0) dtot++; else if(tmp.first == 1) dtot += 2; else dtot += 3; } } if(dtot < len - 20){ int cnt = min((len - 20 - dtot) / 3, ctot); ctot -= cnt; dtot += cnt * 3; } tot = dtot + ctot + max(0, len - 20 - dtot); }else{ tot = add; tot += len - 20; } }else{ if(add <= bdel){ tot = bdel + 6 - len; }else{ tot = add; if(len + add - bdel < 6) tot += 6 - (len + add - bdel); } } return tot; } };
|
