【贪心]【字符串】【分类讨论】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

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