【贪心]【字符串】【分类讨论】420 强密码检验器

本文涉及知识点

贪心字符串分类讨论

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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛