leetcode 420. Strong Password Checker暗号強度検査器+法則を探す+本当にしません

A password is considered strong if below conditions are all met:
It has at least 6 characters and at most 20 characters. It must contain at least one lowercase letter, at least one uppercase letter, and at least one digit. It must NOT contain three repeating characters in a row (“…aaa…” is weak, but “…aa…a…” is strong, assuming other conditions are met). Write a function strongPasswordChecker(s), that takes a string s as input, and return the MINIMUM change required to make s a strong password. If s is already strong, return 0.
Insertion, deletion or replace of any one character are all considered as one change.
この問題はきっとできません.次はネット上の分析です.
まず、非強力な暗号列には主に3つの問題があります.

の長さの問題で、長さが6未満の場合、文字を挿入することで長さを補充し、長さが20を超える場合、文字を削除します.

文字または数字が欠けています.大文字、小文字、数字が欠けている場合は、文字を挿入したり置換したりすることで補完できます.

繰り返し文字、これも本題の最大の難点で、挿入、削除、または置換はすべて繰り返し文字の問題を解決することができて、例えば1つの文字列“aaaa”があって、私達は1回の置換を使って、例えば中間の文字’a’を交換することができます;あるいは、2番目のaと4番目のaの後ろにそれぞれ1つの非a文字を挿入する2回の挿入文字.あるいは、3つのaを削除して重複文字の問題を解決することができます.問題は最小限のステップを必要とするため,置換が最も効率的に文字を繰り返す方法であることが明らかになった.

例を挙げて見ると、この3つの状況は互いに独立していないことがわかります.1つの操作は、文字列「aaa 1 a」のような複数の問題を解決することができます.2番目のaの後ろに「B」を追加し、「aaBa 1 a」になります.これにより、3つの質問を同時に解決しました.つまり、長さを増やし、欠落した大文字を補充し、重複を取り除きました.だから私たちの目標は、このような多くの問題を解決できる操作をできるだけ見つけることです.ケース3(重複文字)は3つの操作で解決できるため,ケース1とケース3を同時に解決でき,ケース2とケース3を同時に解決できる操作をそれぞれ見た.状況1と状況2を同時に解決する操作について、元の暗号列の長さが6未満であると重複するので、状況に分けて議論します.
暗号列の長さが6より小さい場合、ケース1とケース2の操作手順はケース3を完全にカバーすることができ、この場合、重複文字の個数の範囲は[3,5]であり、3つの重複文字がある場合、3文字を増やす操作は、重複文字の問題を同時に解決することができる(「aaa」->「a 1 B Caa」;4つの重複文字がある場合、2文字を増やす操作も重複問題を解決することができる(「aaaaa」->「aa 1 B aa」).5つの重複文字がある場合、追加と置換操作も重複問題を同時に解決します(「aaaaa」->「aaa 1 aaB」).そこで、少なくともどのくらいのステップで状況1と状況2を同時に解決できるかに専念し、まず、現在の暗号列に何文字を補う必要があるかを計算し、6まで文字を補充する方法は挿入文字で操作するしかなく、挿入文字で操作しても状況2を解決することができるので、状況2の欠落種類の個数がdiff以下である場合、操作を増やす必要はありません.diffが欠落した種類の個数を完全にカバーできない場合、両者の差を加えなければならない.
暗号列の長さが6つ以上の場合、この状況は複雑で、現在の文字列の長さが基準を超えても基準を満たさないことはできないため、できるだけ挿入文字で操作しないでください.これは長さが制限を超える可能性があるからです.長さの不確実性のため、大量の重複文字がある可能性があるので、解決状況3が重要になります.前の分析では、置換文字が最も効率的な解法ですが、この方法では解決できません.1、長さが基準を超えた場合、いくら置換文字をしても、長さを減らすことはできませんが、私たちは無脳に文字を削除することはできません.これは必ずしも最低限のステップであるとは限らないので、状況3を解決する際には状況1を総合的に考慮し、ここではtrick(よく考えられる)を用い、重複文字の個数kが3以上の場合、直接2つに削除するのではなく、先に最近の(3 m+2)個に削除すると、kがちょうど3で除去されると、では、私たちは直接k−1になり、kを3で割った場合、k−2になります.このような利点は、3 m+2個の重複文字が最も効率的にm個の文字を置き換えて重複を除去できることである.では、具体的な手順を見てみましょう.まず、20個を超える個数overを算出します.overを結果resに追加します.なぜなら、このover個の削除操作はどうしてもしなければならないからです.超えなければoverは0であり,変数leftで重複文字を解決するために最も置換する必要がある個数を表し,0に初期化する.次に、前の統計文字の個数の配列を巡り、ある文字の個数が3以上で、overが0より大きい場合、個数を最近の3 m+2個に減らし、overも対応して減少します.overが0より小さい場合は、削除操作を行わないでください.すべての重複個数を3 m+2に減らしたが、overが0より大きい場合はさらに削除操作を行い、今回はoverが0以下になるまで3 m個を直接削除し、残りの重複個数が3より大きい文字があれば、置換文字に必要な個数をleftに直接加算すればよい.最後にleftとmissingを比較し、結果resに大きな値を加えればよい、
この接続［LeetCode］Strong Password Checker暗号強度検査器を参照してください.
コードは次のとおりです.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;


class Solution
{
public:
    int strongPasswordChecker(string s) 
    {
        int deleteTarget = max(0, (int)s.length() - 20), addTarget = max(0, 6 - (int)s.length());
        int toDelete = 0, toAdd = 0, toReplace = 0, needUpper = 1, needLower = 1, needDigit = 1;

        for (int l = 0, r = 0; r < s.length(); r++) 
        {
            if (isupper(s[r])) 
                needUpper = 0; 
            if (islower(s[r])) 
                needLower = 0; 
            if (isdigit(s[r])) 
                needDigit = 0; 

            if (r - l == 2) 
            {
                if (s[l] == s[l + 1] && s[l + 1] == s[r]) 
                {
                    if (toAdd < addTarget) { toAdd++, l = r; }
                    else { toReplace++, l = r + 1; }
                }
                else 
                    l++;
            }
        }
        if (s.length() <= 20) 
            return max(addTarget + toReplace, needUpper + needLower + needDigit);

        toReplace = 0;
        vector<unordered_map<int, int>> lenCnts(3);
        for (int l = 0, r = 0, len; r <= s.length(); r++)
        {
            if (r == s.length() || s[l] != s[r]) 
            {
                if ((len = r - l) > 2) 
                    lenCnts[len % 3][len]++;
                l = r;
            }
        }

        for (int i = 0, numLetters, dec; i < 3; i++)
        {
            for (auto it = lenCnts[i].begin(); it != lenCnts[i].end(); it++) 
            {
                if (i < 2) 
                {
                    numLetters = i + 1, dec = min(it->second, (deleteTarget - toDelete) / numLetters);
                    toDelete += dec * numLetters, it->second -= dec;
                    if (it->first - numLetters > 2) 
                        lenCnts[2][it->first - numLetters] += dec; 
                }
                toReplace += (it->second) * ((it->first) / 3);
            }
        }

        int dec = (deleteTarget - toDelete) / 3;
        toReplace -= dec, toDelete -= dec * 3;
        return deleteTarget + max(toReplace, needUpper + needLower + needDigit);
    }
};