【贪心]【字符串】【分类讨论】420 强密码检验器-阿里云开发者社区

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

2024-04-10 33

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

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

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

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。