本文涉及知识点
贪心 字符串 分类讨论
LeetCode420 强密码检验器
满足以下条件的密码被认为是强密码：
由至少 6 个，至多 20 个字符组成。
包含至少 一个小写 字母，至少 一个大写 字母，和至少 一个数字 。
不包含连续三个重复字符 (比如 “Baaabb0” 是弱密码, 但是 “Baaba0” 是强密码)。
给你一个字符串 password ，返回 将 password 修改到满足强密码条件需要的最少修改步数。如果 password 已经是强密码，则返回 0 。
在一步修改操作中，你可以：
插入一个字符到 password ，
从 password 中删除一个字符，或
用另一个字符来替换 password 中的某个字符。
示例 1：
输入：password = “a”
输出：5
示例 2：
输入：password = “aA1”
输出：3
示例 3：
输入：password = “1337C0d3”
输出：0
提示：
1 <= password.length <= 50
password 由字母、数字、点 ‘.’ 或者感叹号 ‘!’ 组成
分类讨论
n = password.length
问题一：字符少于6个。 只能增加。
问题二：字符多余20个。只能删除。
问题三：缺少大写字母、小写字母、数字。编辑或增加，效率一样。
问题三：连续相同字符。编辑的效率最高，插入其次，删除最次。
n < 6
只需要增加，不需要删除和编辑。
3,4个连续相同字符，增加和编辑效率一样。
5个连续字符，两种方案：一，增加2次。二，编辑一次，增加一次。效率一样。
n ∈ \in∈ [6,20]
只需要编辑，不需要增加和删除。
n > 20
不需要增加，增加用编辑代替。
i2= n -20。 处理问题4，至少删除i2次。如果存在3的倍数，删除可以减少用编辑处理问题四的次数。没有3的倍数，% \%% 3 为1的，减少2;否则 % \%% 3 为2的，减少3。
i3 记录缺少的字符类型数量。可以和问题一同处理。
代码
核心代码
class Solution { public: int strongPasswordChecker(string password) { m_c = password.length(); const int i1 = max(0,6 - m_c); const int i2 = max(0, m_c - 20); unordered_set<int> setType; for (const auto& ch : password) { if (islower(ch)) { setType.emplace(1); } if (isupper(ch)) { setType.emplace(2); } if (isdigit(ch)) { setType.emplace(3); } } priority_queue<pair<int, int>,vector<pair<int, int>>,std::greater<>> minHeap; int preIndex = 0; auto Add = [&](const int len) { if (len < 3) { return; } minHeap.emplace(len % 3+1, len); }; auto Total = [&minHeap]() { int iRet = 0; while (minHeap.size()) { iRet += minHeap.top().second / 3; minHeap.pop(); } return iRet; }; const int i3 = 3 - setType.size(); for (int i = 1; i < m_c; i++) { if (password[preIndex] != password[i]) { Add( i - preIndex); preIndex = i ; } } Add(m_c - preIndex); if (i1 > 0) { int i4 = 0; if (minHeap.size() && (minHeap.top().second >= 3)) { i4++; } if (minHeap.size() && (minHeap.top().second >= 5)) { i4++; } return max(max(i1, i3), i4); } if (i2 > 0) { int del = i2; while (minHeap.size() && (del >= minHeap.top().first)) { del -= minHeap.top().first; const int len = minHeap.top().second - minHeap.top().first; minHeap.pop(); Add(len); } return i2 + max(Total(), i3); } return max(i3, Total()); } int m_c; };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<int> nums1, nums2; { Solution sln; ; auto res = sln.strongPasswordChecker("aaa111"); Assert(2, res); } { Solution sln; ; auto res = sln.strongPasswordChecker("aA123"); Assert(1, res); } { Solution sln; ; auto res = sln.strongPasswordChecker("a"); Assert(5, res); } { Solution sln; ; auto res = sln.strongPasswordChecker( "aA1"); Assert(3, res); } { Solution sln; ; auto res = sln.strongPasswordChecker("1337C0d3"); Assert(0, res); } }
2023年5月
class Solution { public: int strongPasswordChecker(string password) { Init(password); if (m_c < 6) {//插入一定由于其它两种 int iInsertForRepeat = 0; for (const auto& it : m_setRepeatNum) { iInsertForRepeat += (it>=5)?2:1; } return max(max(6 - m_c, 3 - m_iTypeNum), iInsertForRepeat); } else if (m_c > 20) {//对应条件1，条件3，修改优化插入；条件2，相同。所以，淘汰插入 //条件1只能删除，条件2只能修改 //3字符重复，删除一个字符，可以减少一次修改,6，9 …字符重复也是 //4字符重复，需要删除2个字符，才能减少一次修改次数，7,10…也是 //5字符重复，需要删除3个字符… int iDoLen = m_c - 20; const int iDoType = 3 - m_iTypeNum; int iNeedDo = iDoLen + iDoType; Do(iDoLen, 0); Do(iDoLen, 1); while ((iDoLen >= 3) && m_setRepeatNum.size()) { Do(iDoLen, 2); } int iReplaceForRepeat = 0; for (const auto& it : m_setRepeatNum) { iReplaceForRepeat += it / 3; } return iNeedDo + max(0, iReplaceForRepeat - iDoType); } else {//替换字符一定优化其它两种 int iReplaceForRepeat = 0; for (const auto& it : m_setRepeatNum) { iReplaceForRepeat += it /3 ; } return max(iReplaceForRepeat, 3 - m_iTypeNum); } } void Do(int& iDoLen,int iMod) { std::unordered_multiset tmp; for (auto& it : m_setRepeatNum ) { if (iDoLen >= iMod+1) { if (iMod == it % 3) { iDoLen -= (iMod + 1); const int iNewRepeatNum = it - (iMod + 1); if (iNewRepeatNum >= 3) { tmp.insert(iNewRepeatNum); } continue; } } tmp.insert(it); } m_setRepeatNum.swap(tmp); } void Init(const string& password) { m_c = password.length(); char preChar = 0; int iRepeatNum = 0; for (int i = 0; i < m_c; i++) { const char& ch = password[i]; if (ch == preChar) { iRepeatNum++; } else { if (iRepeatNum >= 3) { m_setRepeatNum.insert(iRepeatNum); } iRepeatNum = 1; preChar = ch; } m_iAZNum += (ch >= ‘A’) && (ch <= ‘Z’); m_iazNum += (ch >= ‘a’) && (ch <= ‘z’); m_iDigNum += (ch >= ‘0’) && (ch <= ‘9’); } if (iRepeatNum >= 3) { m_setRepeatNum.insert(iRepeatNum); } m_iTypeNum += (m_iAZNum > 0) + (m_iazNum > 0) + (m_iDigNum > 0); } int m_c = 0; int m_iTypeNum = 0; int m_iAZNum = 0; int m_iazNum = 0; int m_iDigNum = 0; std::unordered_multiset m_setRepeatNum;// 重复i次的字符 };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
