一連の首と尾がつながっているビーズ(m個)は、N種類の色(N<=10)があり、アルゴリズムを設計し、その中の1段を取り出し、すべてのN中の色を含み、長さを最短にする必要がある.そして、時間の複雑さと空間の複雑さを分析する.

このテーマはネット上でもうたくさんの大物が書いた.このテーマ自体がおもしろいので、自分の見解を書くつもりです.
内容は文章のタイトルのようです:1列の首と尾のつながっている玉(m個)、N種類の色(N『=10)があって、1つのアルゴリズムを設計して、その中の1段を取り出して、すべてのNの中の色を含んで、そして長さを最も短くすることを要求します.そして時間の複雑さと空間の複雑さを分析します.
ここでは牛客の簡略化されたテーマで説明するつもりです.

    
         ，             ，     ，   ，  ，  ，   。                ，    ，         ，          ，   ，   ，        ，                  ，                ，          。              。                       。

    :
             ，A     ，B     ，C     ，D    ，E    ，F    ，G      ，                          ，          。        。

    :
                。    
  1
  

ABCYDYE
ATTMBQECPD
  

1
3

考え方は大体以下の通りです:ダブルポインタ、ヘッドテールマークheadとtail.ダブルポインタの構想は双方向スキャンであることが多いが、この問題は一方向スキャンである:headとtailは0に初期化され、tailはシーケンスにm種のビーズが現れるまで後ろに進み、現在の長さを記録する.headは一歩前に進み、tail=headになります.tailは、シーケンスにm種のビーズが現在の長さを記録するまで再び前に進み、前回よりも小さい場合は最小長を更新します.そしてシーケンスを巡回するまで繰り返します.最初と最後がつながっているので、シーケンスcopyを一度に接続すれば、最初と最後がつながっている場合を巡回することができます.牛客のテーマに対して、Nは比較的に小さいため5だけ、直接1つのintのバイナリビットを使って表すことができて、つまり:0 x 1 fはすべての種類の宝石がすべて現れるかどうかを代表することができます
次はコードです

#include

using namespace std;

int solve(string str)
{
    int len=str.length();
    str+=str;
    int min_len=len;
    //    5   ，        ，       
    for(int head=0;head5;head++)
    {
        int flag=0;//    
        int len_temp=0;//      ，       
        int tail=head;//   head  ，tail   ，     tail   head     

        while((tail5)&&(flag!=0x1f)){
            if(str[tail]-'A'<5){//            N  1
                flag=flag|(1<str[tail-'A']));
            }

            if(flag==0x1f){//          
                len_temp=head-tail+1;//         while  
                break;
            }

            tail++;//tail     
        }
        if(flag==0x1f){
            //             ，   while  
            //     （        ，      ）
            min_len=min(min_len,len_temp);
        }

    }
    return len-min_len;//             
}

int main()
{
    string str;
    while(cin>>str)
    {
        cout<str)<

賢い人は、牛客の問題から文章の問題にどのように引用するか、今から知っているかもしれません.次のwhileループを抽象化して、N色のビーズが現れたかどうかを判断し、どれだけの色が現れたかを更新する方法です.

while((tail5)&&(flag!=0x1f)){
            if(str[tail]-'A'<5){//            N  1
                flag=flag|(1<str[tail-'A']));
}

同時に後にflagに触れたところを条件を満たすかどうかを修正すればいいので、文章のテーマに引用します.文章のテーマの最終的な時間の複雑さ:O(MN).
また,最初と最後がつながっている場合を遍歴するためには,最初のビーズのシーケンスにシーケンスの先頭のN個のビーズをリンクするだけでよい.空間複雑度O(M+N)
参考資料:牛客網、牛客網牛油たち