LeetCode刷题实战420：强密码检验器

我会带着你远行 2022-09-17 03:26 142阅读 0赞

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 **强密码检验器**，我们先来看题面：

https://leetcode-cn.com/problems/strong-password-checker/

![1deb9ff4f936e36a845126d33c73f87b.png][]

一个强密码应满足以下所有条件：

由至少6个，至多20个字符组成。

至少包含一个小写字母，一个大写字母，和一个数字。

同一字符不能连续出现三次 (比如 "...aaa..." 是不允许的, 但是 "...aa...a..." 是可以的)。

编写函数 strongPasswordChecker(s)，s 代表输入字符串，如果 s 已经符合强密码条件，则返回0；否则返回要将 s 修改为满足强密码条件的字符串所需要进行修改的最小步数。

插入、删除、替换任一字符都算作一次修改。

## **解题** ##

**http://www.manongjc.com/detail/20-zosdnuezjvotflt.html**

这是一道数学题。

连续字符串删除和插入的方式代价高，尽量使用替换。如何理解呢？对于任意>=3的连续串长度为s，所需要的替换次数为s//3，

而使用插入(s-1)/2次操作和删除s-2次。插入和删除相结合还是比替换要慢。

对于长度>=3的连续串，每个修改次数为s//3, s为连续串的长度，记录总的连续串修改次数为n\_modify

记录确实字符个数为n\_lack

length<6，返回max(6-len(s), n\_lack)

length<=20，返回max(n\_modify, n\_lack)

length>20，此时一定要删除字符的长度为n\_delete = len(s) - 20

我们知道连续串可以通过删除字符来减少n\_modify。我们肯定优先删除连续串。对于不同长度的连续串，有这样的特性。

3n，删除一个字符，就可以减少一次替换

3n+1, 删除两个字符，减少一次替换

3n+2, 删除三个字符，减少一个替换

要使得最终结果最小，我们优先考虑3n，多出来的继续考虑3n+1，和3n+2。最终剩下来的都是3n+2，即如果还有剩余就全部用来减少3n+2的替换次数 。

class Solution:
        def strongPasswordChecker(self, s: str) -> int:
            cnt = [0]*3 # 3n, 3n+1, 3n+2
    
            a , A, num = 1, 1, 1
            i = 0
            n_modify = 0
            while i < len(s):
                c = s[i]
                length = 1
                if s[i] >= '0' and s[i] <= '9':
                    num = 0
                elif s[i] >= 'a' and s[i] <= 'z':
                    a = 0
                elif s[i] >= 'A' and s[i] <= 'Z':
                    A = 0
                i += 1            
                while i < len(s) and s[i] == c:
                    i += 1
                    length += 1 
                if length >= 3:
                    n_modify += length//3
                    cnt[length%3] += 1
                    
            n_lack = a + A + num
            if len(s) < 6:
                return max(n_lack, 6-len(s))
            if len(s) <= 20:
                return max(n_lack, n_modify)
    
            n_delete = len(s) - 20
    
            if n_delete <= cnt[0]:
                return max(n_modify - n_delete, n_lack) + n_delete
    
            if (n_delete - cnt[0]) <= 2*cnt[1]:
                return max(n_modify - cnt[0]- (n_delete-cnt[0])//2, n_lack) + n_delete
    
            if (n_delete - cnt[0] - 2*cnt[1]) <= 3 * cnt[2]:
                return max(n_modify - cnt[0] - cnt[1]- (n_delete - cnt[0] - 2*cnt[1])//3, n_lack) + n_delete;
            return max(n_modify - cnt[0] - cnt[1] - cnt[2] - (n_delete - cnt[0] - 2*cnt[1] 
                       -3*cnt[2])//3, n_lack) + n_delete;

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个**在看**或者转发吧，你们的支持是我最大的动力 。

**上期推文：**

[LeetCode1-400题汇总，希望对你有点帮助！][LeetCode1-400]

[LeetCode刷题实战401：二进制手表][LeetCode_401]

[LeetCode刷题实战402：移掉 K 位数字][LeetCode_402_ K]

[LeetCode刷题实战403：青蛙过河][LeetCode_401]

[LeetCode刷题实战404：左叶子之和][LeetCode_404]

[LeetCode刷题实战405：数字转换为十六进制数][LeetCode_401]

[LeetCode刷题实战406：根据身高重建队列][LeetCode_401]

[LeetCode刷题实战407：接雨水 II][LeetCode_401]

[LeetCode刷题实战408：有效单词缩写][LeetCode_401]

[LeetCode刷题实战409：最长回文串][LeetCode_409]

[LeetCode刷题实战410：分割数组的最大值][LeetCode_401]

[LeetCode刷题实战411：最短独占单词缩写][LeetCode_401]

[LeetCode刷题实战412：Fizz Buzz][LeetCode_412_Fizz Buzz]

[LeetCode刷题实战413：等差数列划分][LeetCode_401]

[LeetCode刷题实战414：第三大的数][LeetCode_414]

[LeetCode刷题实战415：字符串相加][LeetCode_401]

[LeetCode刷题实战416：分割等和子集][LeetCode_401]

[LeetCode刷题实战417：太平洋大西洋水流问题][LeetCode_417]

[LeetCode刷题实战418：屏幕可显示句子的数量][LeetCode_417]

[LeetCode刷题实战419：甲板上的战舰][LeetCode_419]

![f890f529841770796aeb85981217a088.png][]

[1deb9ff4f936e36a845126d33c73f87b.png]: /images/20220828/d6dd4f6ef97c400b9b78bcda1856d13e.png
[LeetCode1-400]: https://blog.csdn.net/itcodexy/article/details/109832160
[LeetCode_401]: https://blog.csdn.net/itcodexy/article/details/120916108
[LeetCode_402_ K]: https://blog.csdn.net/itcodexy/article/details/120610243
[LeetCode_404]: https://blog.csdn.net/itcodexy/article/details/118402082
[LeetCode_409]: https://blog.csdn.net/itcodexy/article/details/114986911
[LeetCode_412_Fizz Buzz]: https://blog.csdn.net/Jackshijin/article/details/103489372
[LeetCode_414]: https://blog.csdn.net/itcodexy/article/details/120858189
[LeetCode_417]: https://blog.csdn.net/itcodexy/article/details/120944809
[LeetCode_419]: http://mp.weixin.qq.com/s?__biz=MzA5NzgzODI5NA==&mid=2454072956&idx=5&sn=519899adc6f6b57b07a479d77b49e99a&chksm=87283bc5b05fb2d3f0307d984f1b44d260f059fa2fe2a0893d14bd92c1dacffcb6166240edb2&scene=21#wechat_redirect
[f890f529841770796aeb85981217a088.png]: /images/20220828/6108ea12e92347c6a755aa46a8397cd4.png