网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 420. 强密码检验器 ，难度为 困难。
Tag : 「模拟」
如果一个密码满足下述所有条件，则认为这个密码是强密码：
- 由至少 66 个，至多 2020 个字符组成。
- 至少包含一个小写字母，一个大写字母，和一个数字。
- 同一字符不能连续出现三次 (比如
"...aaa..."是不允许的, 但是"...aa...a..."如果满足其他条件也可以算是强密码)。
给你一个字符串 password，返回将 password 修改到满足强密码条件需要的最少修改步数。如果 password 已经是强密码，则返回 00 。
在一步修改操作中，你可以：
- 插入一个字符到
password， - 从
password中删除一个字符，或 - 用另一个字符来替换
password中的某个字符。
示例 1：
输入：password = "a" 输出：5 复制代码
示例 2：
输入：password = "aA1" 输出：3 复制代码
示例 3：
输入：password = "1337C0d3" 输出：0 复制代码
提示：
- 1 <= password.length <= 501<=password.length<=50
password由字母、数字、点'.'或者感叹号'!'
模拟（分情况讨论）
这是一道麻烦而又没啥意义的题。
需要满足的条件有三个，根据 password 的长度 nn，字符种类数量 mm，以及相同字符连续长度不低于 33 的情况 gg（数组 gg 的长度为相同字符长度不低于 33 的连续段个数，g[i]g[i] 代表第 ii 个连续段的长度），进行分情况讨论：
- n < 6n<6：长度过短，不满足要求，任何一次「删除」操作都需要额外搭配一个「增加」操作，而这两步操作可以使用「替换」来代替，结果不会变差；同时为了满足长度要求，我们必然要使用到「增加」操作。因此需要用到「增加」和「替换」操作，枚举所有的情况发现，最少操作次数最终可以归纳到 \max(6 - n, 3 - m)max(6−n,3−m)；
- 6 \leqslant n \leqslant 206⩽n⩽20：任何的有效的「增加」操作目的只能是为了「破坏连续段长度不低于 33」或者「增加字符种类数量」，这两个目的都可以使用「替换」来做到；而任何有效的「删除」操作只能是为了「破坏连续段长度不低于 33」，这一目的也可以使用「替换」来做到。因此只需要用到「替换」操作，结果不会变差。对于某个 g[i]g[i] 而言，我们需要使用 \left \lfloor \frac{g[i]}{3} \right \rfloor⌊3g[i]⌋ 次「替换」操作来满足「连续段长度不能不低于 33」的要求，在此基础上再考虑字符种类的问题，最少操作次数最终可以归纳到 \max(\sum_{i = 0}^{g.length - 1}\left \lfloor \frac{g[i]}{3} \right \rfloor, 3 - m)max(∑i=0g.length−1⌊3g[i]⌋,3−m)；
- n > 20n>20：长度过长，不满足要求，任何一次「增加」操作都需要额外搭配一个「删除」操作，只需要用到「删除」和「替换」操作，为了满足长度要求，必然用到的「删除」操作可能会影响到最终的「替换」操作，直觉上，应当优先删除那些「连续段长度不低于 33」的字符。由于连续段长度 g[i]g[i] 与其消耗的「替换」次数的关系为 \lfloor \frac{g[i]}{3} \rfloor⌊3g[i]⌋，在不考虑余数的情况下，每删除 33 个字符，能够连带的减少一次「替换」操作。因此我们可以根据 g[i]g[i] 对 33 取模进行统计，得到 cntscnts 数组（cntscnts 数组长度为 33，其中 cnts[i] = xcnts[i]=x 含义为在所有「连续段长度不低于 33」的连续段中，长度余数为 ii 的数量有 xx 个），按照余数从小到大的优先级进行同步抵消，得到最终的「替换」操作数 tottot（tottot 起始值为 \sum_{i = 0}^{g.length - 1}\left \lfloor \frac{g[i]}{3} \right \rfloor∑i=0g.length−1⌊3g[i]⌋）。除了可变的「替换」操作以外，我们不可避免还需要 base = n - 20base=n−20 的「删除」操作，最少操作次数可以归纳到 base + \max(tot, 3 - m)base+max(tot,3−m)
实现上，我们并不需要真正处理出来 gg 数组，可以边统计「连续段长度不低于 33」边累加需要的「替换」次数。
代码：
class Solution { public int strongPasswordChecker(String password) { char[] cs = password.toCharArray(); int n = cs.length; int A = 0, B = 0, C = 0; for (char c : cs) { if (c >= 'a' && c <= 'z') A = 1; else if (c >= '0' && c <= '9') B = 1; else if (c >= 'A' && c <= 'Z') C = 1; } int m = A + B + C; if (n < 6) { return Math.max(6 - n, 3 - m); } else if (n <= 20) { int tot = 0; for (int i = 0; i < n; ) { int j = i; while (j < n && cs[j] == cs[i]) j++; int cnt = j - i; if (cnt >= 3) tot += cnt / 3; i = j; } return Math.max(tot, 3 - m); } else { int tot = 0; int[] cnts = new int[3]; for (int i = 0; i < n; ) { int j = i; while (j < n && cs[j] == cs[i]) j++; int cnt = j - i; if (cnt >= 3) { tot += cnt / 3; cnts[cnt % 3]++; } i = j; } int base = n - 20, cur = base; for (int i = 0; i < 3; i++) { if (i == 2) cnts[i] = tot; if (cnts[i] != 0 && cur > 0) { int t = Math.min(cnts[i] * (i + 1), cur); cur -= t; tot -= t / (i + 1); } } return base + Math.max(tot, 3 - m); } } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.420 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
