2ポインタアルゴリズムを学んでLeetCodeをプレイする

[[421659]]

みなさんこんにちは。私は梁唐です。

今日は、非常に古典的で非常にシンプルなアルゴリズムについてお話します。このアルゴリズムを学習しても、LeetCode をマスターできるわけではありませんが、多くの問題を解決できます。また、他の多くのアルゴリズムでも同様の考え方が採用されており、参考として非常に有意義です。

このアルゴリズムの名前は 2 ポインターアルゴリズムと呼ばれ、英語名は two pointers です。

アルゴリズムの原理

このアルゴリズムは 2 つのポインターと呼ばれているので、名前が示すように 2 つのポインターに関連している必要があります。

まず最初に述べておきたいのは、ここでのポインタは、従来の意味でのポインタではないということです。これは、場所を記録する変数またはマークとして理解できます。 2 つの変数を使用して線形リスト内の 2 つの位置を記録し、これら 2 つの位置で囲まれた間隔を維持します。たとえば、区間の左側の変数が l と呼ばれ、右側の変数が r と呼ばれる場合、維持されるのは区間 [l, r] です。

したがって、2 つのポインタの目的は間隔を維持することであり、これはこのアルゴリズムの中心的な目的でもあります。したがって、このアルゴリズムの一般的な適用シナリオは、合法的な最大間隔を見つけることです。もちろん、実際の問題は、私が求めているのは法的な範囲であると直接教えてくれるわけではありません。その代わりに、さまざまな方法でパッケージ化され、紆余曲折が与えられます。分析と理解を通じて、問題の核心的な要求を把握する必要があります。

アルゴリズムの核となる目的を理解すると、その原理を理解するのがはるかに簡単になります。解決すべき問題は 1 つだけです。それは、間隔をどのように維持するかということです。

l と r は現在、正当な位置に留まっていると仮定し、[l, r] を間隔として理解しているので、l と r の変化は間隔の移動と見なすことができます。

たとえば、l が増加すると、間隔の左側が縮小することがわかります。 [l, r] から [l+1, r] に進みます。これは、要素が区間の左側からポップされることを意味します。逆に、r が増加すると、区間の右側が [l, r] から [l, r+1] に再度拡張され、区間の右側に新しい要素が追加されることを意味します。したがって、l と r の増加を制御することは、間隔内の要素の追加と削除を制御することと同じです。

移動したいときは、r を 1 ビット増やします。つまり、間隔に要素を追加します。新しい要素が追加されたため、間隔の正当性が侵害される可能性があります。区間の正当性を維持するために何かを行う必要があります。たとえば、正当性が回復されるまで、l を左側に移動して区間から要素を取り出すことができます。

r が少しずつ移動すると、すべての合法的な間隔を自然に横断し、他の最大値または最小値を見つけるのは非常に簡単になります。

文章は少し抽象的に見えるかもしれませんが、問題ありません。具体的な例を見て、学んだアルゴリズムを適用してみましょう。

例

LeetCode の 3 番目の質問を例に挙げてみましょう。この問題では、繰り返し文字を含まない文字列内で最長の部分文字列を見つける必要があります。

表面的には、これは文字列の問題であり、多くの人の考えはおそらく文字列を中心に展開されます。しかし実際には、探している部分文字列を元の文字列上の区間として見なすだけでよいため、これは最大の合法的な区間を見つける問題です。

この問題では、合法性とは、間隔内の文字が異なることを意味します。

実際、それはすでに非常に明白です。 2 つのポインタアルゴリズムを適用するだけです。まず、合法的な区間を初期化します。この問題では、合法的な区間は [0, 0] になると考えるのが簡単です。後続の各ステップでは、r を 1 つ右に移動します。つまり、間隔に新しい文字を挿入します。新しい文字を挿入すると、間隔の正当性が失われ、文字が繰り返される可能性があります。

この場合、l ポインタを移動し、間隔が再び有効になるまで間隔内の要素をポップアウトします。区間の正当性が回復されたかどうかを判断するには、区間内の各要素の数を格納するマップを使用する必要があります。新しく挿入された文字の数が 1 より大きい場合、その数が 1 に戻るまで正当性が侵害されていることを意味します。

コード

少し抽象的すぎるかもしれませんが、問題ありません。コードを使って説明してみましょう。

クラスソリューション{
公共：
 int lengthOfLongestSubstring(文字列 s) {
        map< char , int > mp;
        s.size () == 0 の場合は0 を返します。
戻り値:
整数l = 0;
        mp[s[0]] = 1;
        // r を 1 つずつ移動して要素を挿入します
( int r = 1; r < s.size ( ); r++) {
 char c = s[r];
            // s[r]をマップに挿入する
            mp [c]++の場合;
それ以外の場合mp[c] = 1;
            // マップ内のs[r]の数が1より大きい場合、競合が発生したことを意味します
            // 正当性が回復するまで左の要素をポップアップします
            （mp[c] > 1）の間{
                mp[s[l++]] --;  
            }
            ret = max (r - l + 1,ret);
        }
 retを返します。
    }
 };

コードコメントと組み合わせると、全体的なロジックは比較的明確になります。

右に拡大し、左に縮小する処理です。さらにややこしいのは、なぜこのようにして最大区間が見つかるのか、という点です。実は、その中に貪欲法の考え方も隠されているのですが、考えるほうが難しいです。

数学的帰納法を使って簡単な証明を行うことができます。まず、[0, 0] が 0 を右端点として見つけられる最大の合法的な区間であることは明らかです。

[l, r] は r を右境界として見つけることができる最大の合法的な間隔であると仮定します。つまり、l は拡張できる最も左の位置です。次に、r を r+1 に移動し、r+1 を右の境界として、左の最大合法間隔を探します。見つかった左の境界は l' と呼ばれます。 l' が l より小さい可能性はありますか?

明らかに、これは不可能です。なぜなら、l' < l の場合、[l', r] も合法であるはずであり、これは私たちの仮定と矛盾するからです。したがって、l' は l 以上でなければなりません。これは、このような再帰アルゴリズムを通じて見つけた間隔がすべて、右側のエンドポイントに基づく最大合法間隔であることを証明しています。右側のエンドポイントを構成する可能性のある各位置に基づいて最大合法間隔を見つけましたが、グローバル最大合法間隔はその中にあるはずです。

最適化

上記のコードを記述したり理解したりできる場合は、2 つのポインターアルゴリズムの理解はかろうじて合格したとみなすことができますが、まだ終わりではありません。

なぜなら、十分に深く理解すれば、この問題をさらに最適化する余地がまだあることがわかるからです。さらなる最適化の前提は、アルゴリズムの理解に依存します。

では、どこを最適化すればよいのでしょうか? 実はとても簡単です。赤い枠でマークすればわかります。

間隔の正当性を維持するため、while ループを使用して左の境界をポップアップしました。よく考えてみてください。while ループを使用する目的は何でしょうか。区間の左境界 l を移動するためです。l を移動する目的は何でしょうか。区間の正当性を維持するためです。では、区間の正当性を維持するための核心は何でしょうか。それは s[r] と同じ文字を取り出すことです。

ここでポイントとなるのは、s[r]と同じ文字をポップアップすることです。何が考えられますか? 本質的な目的は、競合の原因となっている文字をポップアウトすることなので、1 つずつ移動させる以外に方法はないでしょうか? すでにマップを使用しているので、それを使用して各文字の位置を記録することはできますか? もちろんです! この方法では、ループの複数回の実行を 1 回の検索に置き換え、プロセスを大幅に高速化します。

もう少し賢ければ、キャラクターの位置を記録するだけなので、実際には地図を使用する必要はないと考えることができます。 ASCII コードの文字範囲は非常に狭いため、配列を使用して保存することができます。これにより、検索が高速化されます。

最適化されたコードを見てみましょう。

クラスソリューション{
公共：
 int lengthOfLongestSubstring(文字列 s) {
整数mp[128];
        memset(mp, -1, mpのサイズ);
        s.size () == 0 の場合は0 を返します。
戻り値:
整数tmp = 0;
整数l = 0;
        mp[s[0]] = 0;
 int n = s.size ( );
 ( int r = 1; r < n; r++)の場合{
 char c = s[r];
            mp[c] >= l の場合 l = mp[c]+1;
            mp[c] = r;
            ret = max (r - l + 1,ret);
        }
 retを返します。
    }
 };