最近开始佛系刷题，为什么说是佛系呢？因为实在是没什么时间，我属于那种有空就做两道，没空就算了的心态，从来不急着催促自己一定要马上干完一件事情。凡事都是能慢则慢的原则，因为我始终认为最好一件事的关键不在于速度，而在于质量。这也是欲速则不达的道理。但慢并不代表拖沓，刷的每一道题我都会认真地分析总结，虽然不能保证是最优解，但绝对是原创并且易懂的代码。另外，本人并非技术大神，上不知天文，下也不懂地理，只有区区十几年的码农经验，惭愧至极。如有大仙在此路过，望指点一二。若为同路修道之好，也望交能易作，共同进步。
闲话略过，进入正题。
LeatCode 420 Strong Password
A password is considered strong if below conditions are all met:
- It has at least 6 characters and at most 20 characters.
- It must contain at least one lowercase letter, at least one uppercase letter, and at least one digit.
- It must NOT contain three repeating characters in a row (“…aaa…” is weak, but “…aa…a…” is strong, assuming other conditions are met).
Write a function strongPasswordChecker(s), that takes a string s as input, and return the MINIMUMchange required to make s a strong password. If s is already strong, return 0.
Insertion, deletion or replace of any one character are all considered as one change.
题目大意：强密码验证
强密码条件
- 长度在6-20位。
- 密码必须包含至少一个大写字母，一个小写字母和一个数字。
- 不能连续使用3个及以上重复字符。
求：通过增加，删除或者修改字符将原始密码修改为强密码的最少次数。
举个例子，123456ab
这个8位密码包含了数字及小写字母，但缺少大写，所以将任意一位修改为大写即可达到要求。所以结果应为1。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=420
分析：
本题目在leetcode中难易度排名第五，解题前应该充分分析出所有可能存在的分支。
简单来看，强密码的要求中包含，长度要求，字符种类要求以及连续字符最大长度要求三类，满足上述三个需求即可视为强密码。在不考虑最优解的前提下，将任意一个字符串修改为强密码的次数可以简单的认为是下列三组修改次数之和：
1.长度修改次数。如果长度大于20或者小于6，那么，密码长度与20或者6的差就是需要修改长度的最小次数。（每增加一位或减少一位，次数加一）
// 密码总长度 int length = s.length(); int changeCount = length - 6; // 长度修改所需最少次数 or int changeCount = 20 - length; // 长度修改所需最少次数
2.添加字符种类次数。字符种类需要包含大写，小写字母及数字。这三少一种，就需要修改一次。
// 如果没有大写字母，字符种类修改次数加一
if(!hasUpperCase){
changeCount ++;
}
// 如果没有小写字母，字符种类修改次数加一
if(!hasUpperCase){
changeCount ++;
}
// 如果没有数字，字符种类修改次数加一
if(!hasDigtal){
changeCount ++;
} 3.重复字符修改次数。修改连续的重复字符时，比如AAAAA，五个A，我们可以通过删除其中3个A（修改次数为3，结果AA），或者通过改变中间一个字符（
修改次数为1，结果AABAA）来达到目的，但是显然后一种方法更为简便，在高效完成任务的同时，还没有更改字符的长度。注意，在不得已的情况下，尽量不要添加或者删减字符，这样会造成长度越界（大于20或小于6）从而产生二次判断。因此，我们可以简单的推算出，任意长度的重复字符中，只需要将每三个相邻的字符中的最右位修改为其他字符即可。例：AAAAAAAAAA，十个A，为了方便观看，我们将其分为几个部分，中间用空格隔开，AAA AAA AAA A，再将相邻的三个A的最右位替换为其他字符，即： AAB AAB AAB A， 修改次数为3，也就是length / 3。
changeCount = repeatingCount / 3;
到此为止，所有的修改策略都分析完了，总的修改次数应该是：
长度修改次数 + 添加字符种类次数 + 重复字符修改次数但是，这只是最简单的分析，题目要求我们得出最少修改次数，而我们算出的是最多次数。因此接下来要考虑如何缩减步骤，这也是算法思路优化的关键！
修改次数合并
其实不难发现，有些修改是可以合并的，例如这个密码，AAAaa。它有三处不符合要求， 长度小于6，没有数字， AAA重复。按照上文的步骤，我们需要三次才能将其修改成为强密码。但是仔细分析发现，我们可以在大写字母A之间加入一个数字，这样仅仅一次就可修改成功。 A6AAaa。
那么，我们来总结下，那些修改步骤可以合并？
- 密码缺少位数，缺少字符种类。这种情况下，我们可以用缺少的字符种类个数N1去填充密码缺少的位数 N2，当然这两个数字N1和N2并不一定相等，所以合并后的次数应为：Max(N1, N2);
- 密码缺少位数，密码中有重复字符。同上，我们可以将缺少的位数填充到重复字符的中间来达到合并的效果。 Max(N1, repeatingCount / 3);
- 缺少字符种类，密码中有重复字符。这和上一种情况也非常类似，有一点需要注意的是，我们说过在不得已的情况下尽量不要增减密码的长度，这里，在密码长度符合要求的前提下，我们可以考虑将重复字符中的某一位替换成缺少的字符种类即可。 Max(缺少字符种类数N1, repeatingCount / 3);
- 密码超过位数，密码中有重复字符。 这应该是本体难点的核心所在！也是接下来我要重点分析的部分。前方高能预警！
密码超过位数和密码中有重复字符该如何合并？
我开始只是单纯的认为密码超过位数和缺少位数的情况是一致的。比如密码中存在AAAA，4个A，并且密码长度超位为1（共21位）， 那么，Max(1, 4 / 3) = 1;就可以了。其实并不然。少位数我们可以在连续字符中增加一个字符解决（AABAA），但是多位数的情况下，减去一位并不能解决问题（AAA），那么这种情况就无法合并了吗？
其实仍然可以合并，只不过要稍微复杂一点罢了。我们还是需要分几种情况来分析。
首先明确的一点是，题目要求不能连续有3个字符重复，也就是说连续2个字符以下是可以的。还是从最简单的逻辑开始考虑，如果连续字符的长度减去密码长度大于20位的位数能够小于等于2，那么就可以合并。
if(repeatingCount - overLength >= 2){
// do merge….
} 但是，这种合并相对于之前的合并效率是比较低的，比如5个A，我们只需要增加一位或是修改一位即可到达要求，然而删除字符处理我们则需要至少删除3位才可以。所以，重点来了，如何删除才能效率最大化这是我们要考虑的重中之重！我们通过举例子来说明。
例子：abcdefgAAABBBB0123456
这个密码长度为21，超一位，并且存在两组重复字符串，AAA和BBBB。字符种类符合要求。这时我们需要减少一位并且消灭重复字符，因此在重复字符中删除一位是最方便的，那么问题来了，这一位是应该删除3A还是4B中的一位呢？秉承利益最大化的前提，显然，将AAA删减为AA是最划算的，这样，重复字符串就只剩下4B了。为什么会这样呢？我们在上文讲过，将一个连续字符串修改为不连续的最少次数是：repeatingCount / 3，当 repeatingCount为3的倍数时，除以3的余数为0，这时将repeatingCount自身减去1再除以3，结果必将小于原先。反过来思考，如果 repeatingCount 不是3的倍数，也就是 repeatingCount / 3 的余数大于0，这样将 repeatingCount – 1之后再除以3对结果是没有影响的（比如8/3等于2, 7/3也等于2）。因此，结论是，将长度为3的倍数的重复字符串减去一位，可以优化结果。
延伸思考一下，同理，如果重复字符创的长度不是3的倍数，那么， 减去（余数 + 1）位可以达到同样的效果。比如重复字符串长度为8，那么8%3=2，8-(2+1)/3=1。
整体的思路到此就算分析完了，我们总结一下。
- 当只有密码长度不符合要求时，按照多退少补的原则，给出的密码长度与要求长度上限或者下限的差，就是最小修改次数。
- 当仅缺少字符种类时，修改一位其他字符为缺少字符即可。最小修改次数为缺少的字符种类数。
- 当仅存在重复字符串时，最小修改次数为：重复字符串长度 / 3。
- 当上述问题同时存在时，有些次数可以合并。（但注意不要重复合并）
作为码农，最开心的莫过是写代码了，既然思路已经清晰，我们看看代码该怎么写。
首先，我们要知道这个给出的密码字符串到底是个什么情况，分析一下他的构成（查户口啦）。
// 为了方便操作，将参数密码字符串转为char数组
char[] cArray = s.toCharArray();
// 得到密码长度
int length = cArray.length;
// 判断重复字符串长度的起始index
int nextCheckRepeatingIndex = 0;
// 开始循环啦。。。
for (int i = 0; i < length; i++) {
char c = cArray[i];
if (c >= 'a' && c <= 'z') {
// 小写字母
lowercaseCount++;
} else if (c >= 'A' && c <= 'Z') {
// 大写字母
uppercaseCount++;
} else if (c >= '0' && c <= '9') {
// 数字
digitCount++;
}
// 避免同一重复字符串被多次记录
if (i >= nextCheckRepeatingIndex) {
int repeatingCount = 1;
// 从当前位开始到密码结束，看有多少位和当前字符连续重复
for (int j = i; j < length; j++) {
if (j < length - 1 && (c ^ cArray[j + 1]) == 0) {
// 记录重复字符串长度
repeatingCount++;
// 设置下一重复字符串检测开始位置
nextCheckRepeatingIndex = j;
} else {
break;
}
}
// 如果重复字符串长度大于等于3，则将该长度计入数组repeatingList，为之后使用。
if (repeatingCount >= 3) {
repeatingList.add(repeatingCount);
}
}
} 这段代码很简单，遍历了一遍该密码字符串，看看它的长度，是否包含大小写以及数字，另外还将它存在的所有重复字符串的长度存到了一个数组。其中有句代码稍微说明下，(c ^ cArray[j + 1]) == 0，这里用到了位运算，符号 ^ 代表位异或运算符，两个相同字符的位异或等于0。当然这里完全可以写成 c == cArray[j + 1]。关于位运算的相关技巧以后有时间我会单独总结一篇博客来讲。
接下来开始修改密码为强密码。如果密码长度符合要求，并且包含大小写及数字，另外也不存在重复字符串，那么该密码已经是强密码不需修改，所以返回0。
if (length >= 6 && length <= 20 && lowercaseCount > 0 && uppercaseCount > 0
&& digitCount > 0 && repeatingList.size() == 0) {
return fixCount;
} 根据上面对密码字符串的构成分析，计算出缺少的字符种类数。
int caseAndDigitErrCount = 0;
if (lowercaseCount == 0) {
caseAndDigitErrCount++;
}
if (uppercaseCount == 0) {
caseAndDigitErrCount++;
}
if (digitCount == 0) {
caseAndDigitErrCount++;
} 如果密码长度小于6：
if (length < 6) {
// 密码缺少的位数
int diff = 6 - length;
// 密码缺少位数，缺少字符种类数，以及消除重复字符串处理的次数可以合并，所以求出他们的最大值即可。
// getNeedFixRepeatingCount()是计算消除重复字符串处理的次数的函数
fixCount = Math.max(caseAndDigitErrCount, Math.max(diff,
getNeedFixRepeatingCount()));
} 如果密码长度在6-20之间：
else if (length >= 6 && length <= 20) {
// 密码长度符合要求，所以求出缺少字符种类数，以及消除重复字符串处理的次数的最大值即可
fixCount = Math.max(getNeedFixRepeatingCount(), caseAndDigitErrCount);
}
密码长度大于20，这也是上文将思路时提到的最复杂的部分。
else {
// 密码多出的位数
int diff = length - 20;
// 合并缺少字符种类数和消减重复字符串处理次数。
int caseAndDigitErrCountForLoop = caseAndDigitErrCount;
while (repeatingList.size() > 0) {
// 计算出消灭一个重复字符串所用的最少次数。
int needFixRepeatingCount = repeatingList.get(0) / 3;
// 如果缺少字符种类数大于等于当前重复字符串的修改数，则当前重复字符串已被消灭，可以从list中移除。
if (caseAndDigitErrCountForLoop >= needFixRepeatingCount) {
caseAndDigitErrCountForLoop -= needFixRepeatingCount;
repeatingList.remove(0);
} else {
// 如果缺少字符种类数小于当前重复字符串的修改数，则重复字符串的长度应变为元长度减去缺少字符种类数已消化的长度。
repeatingList.set(0, repeatingList.get(0) - caseAndDigitErrCountForLoop * 3);
break;
}
}
// 合并密码多出的位数和消减重复字符串处理次数。
int diffForLoop = diff;
if (diffForLoop > 0) {
mergeDiffAndRepeat(diffForLoop);
}
// 合并后的次数相加即为总次数（此时已不存在可以合并的次数了）
fixCount = diff + caseAndDigitErrCount + getNeedFixRepeatingCount();
} 最后看看如何合并密码多出的位数和消减重复字符串处理次数。思路上面已经提到过了，这里再简单啰嗦下，把多余的位数减到哪个重复字符串上是效率的关键，首选是除以三余数为0的减1位，然后是除以三余数为1的减2位，再之后是余数为2的减3位，这样减过一圈之后，所有的重复字符串长度应该都是余数为2才对！如果密码总长度仍大于20，并且重复字符串仍然存在，继续重复之上的操作。本方法使用到递归。
int remainder = 0; // 余数
private void mergeDiffAndRepeat(int diff) {
// 消耗的diff长度为余数加1
// diff为密码字符串超出的位数
int cost = remainder + 1;
if (diff == 0 || repeatingList.size() == 0 || diff < cost) {
return;
}
List removeListt = new ArrayList<>();
for (int i = 0; i < repeatingList.size(); i++) {
int repeat = repeatingList.get(i);
if (repeat < 3) {
removeListt.add(repeat);
continue;
} if (diff < cost) {
break;
} if (repeat % 3 == remainder) {
repeatingList.set(i, repeat - cost);
diff -= cost;
if (diff == 0) {
return;
}
}
}
for (int rid : removeListt) {
repeatingList.remove(Integer.valueOf(rid));
}
remainder++;
if (remainder == 3) {
remainder = 0;
}
mergeDiffAndRepeat(diff);
} 最后是完整代码：
int lowercaseCount = 0;
int uppercaseCount = 0;
int digitCount = 0;
List<Integer> repeatingList = new ArrayList<>();
public int strongPasswordChecker(String s) {
char[] cArray = s.toCharArray();
int length = cArray.length;
int nextCheckRepeatingIndex = 0;
for (int i = 0; i < length; i++) {
char c = cArray[i];
if (c >= 'a' && c <= 'z') {
lowercaseCount++;
} else if (c >= 'A' && c <= 'Z') {
uppercaseCount++;
} else if (c >= '0' && c <= '9') {
digitCount++;
}
if ((i + 2 < length) && i >= nextCheckRepeatingIndex) {
int repeatingCount = 1;
for (int j = i; j < length; j++) {
if (j < length - 1 && (c ^ cArray[j + 1]) == 0) {
repeatingCount++;
nextCheckRepeatingIndex = j;
} else {
break;
}
}
if (repeatingCount >= 3) {
repeatingList.add(repeatingCount);
}
}
}
return fixPw(s);
}
private int fixPw(String s) {
int length = s.length();
int fixCount = 0;
if (length >= 6 && length <= 20 && lowercaseCount > 0 && uppercaseCount > 0 && digitCount > 0
&& repeatingList.size() == 0) {
return fixCount;
}
int caseAndDigitErrCount = 0;
if (lowercaseCount == 0) {
caseAndDigitErrCount++;
}
if (uppercaseCount == 0) {
caseAndDigitErrCount++;
}
if (digitCount == 0) {
caseAndDigitErrCount++;
}
if (length < 6) {
int diff = 6 - length;
fixCount = Math.max(caseAndDigitErrCount, Math.max(diff, getNeedFixRepeatingCount()));
} else if (length >= 6 && length <= 20) {
fixCount = Math.max(getNeedFixRepeatingCount(), caseAndDigitErrCount);
} else {
int diff = length - 20;
int caseAndDigitErrCountForLoop = caseAndDigitErrCount;
while (repeatingList.size() > 0) {
int needFixRepeatingCount = repeatingList.get(0) / 3;
if (caseAndDigitErrCountForLoop >= needFixRepeatingCount) {
caseAndDigitErrCountForLoop -= needFixRepeatingCount;
repeatingList.remove(0);
} else {
repeatingList.set(0, repeatingList.get(0) - caseAndDigitErrCountForLoop * 3);
break;
}
}
int diffForLoop = diff;
if (diffForLoop > 0) {
mergeDiffAndRepeat(diffForLoop);
}
fixCount = diff + caseAndDigitErrCount + getNeedFixRepeatingCount();
}
return fixCount;
}
int remainder = 0;
private void mergeDiffAndRepeat(int diff) {
int cost = remainder + 1;
if (diff == 0 || repeatingList.size() == 0 || diff < cost) {
return;
}
List<Integer> removeListt = new ArrayList<>();
for (int i = 0; i < repeatingList.size(); i++) {
int repeat = repeatingList.get(i);
if (repeat < 3) {
removeListt.add(repeat);
continue;
}
if (diff < cost) {
break;
}
if (repeat % 3 == remainder) {
repeatingList.set(i, repeat - cost);
diff -= cost;
if (diff == 0) {
return;
}
}
}
for (int rid : removeListt) {
repeatingList.remove(Integer.valueOf(rid));
}
remainder++;
if (remainder == 3) {
remainder = 0;
}
mergeDiffAndRepeat(diff);
}
private int getNeedFixRepeatingCount() {
int count = 0;
for (int i : repeatingList) {
count += (i / 3);
}
return count;
} 本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-420-strong-password-checker（密码强度检查）-思路分析及java源码-2/
View Comments (1)
666