Leetcode の基本アルゴリズム: スライディングウィンドウについてお話しましょう

[[434663]]

序文

LeetCode を練習していると、スライディングウィンドウタイプの問題によく遭遇します。スライディングウィンドウの問題は非常に古典的かつ技術的であり、一般的に大企業で出題されます。今日は、スライディングウィンドウのルーチンを学びましょう。記事に間違いがあれば、指摘してください。ありがとうございます〜

スライディングウィンドウとは何ですか?
アルゴリズムの問題がスライディングウィンドウに入る
スライディングウィンドウを使用するとどのような問題を解決できますか?
スライディングウィンドウフレームルーチン
Leetcode ケース分析

スライディングウィンドウとは何ですか?

スライディングウィンドウという言葉は誰もが知っていると思います。 TCP について話すとき、私たちはしばしばスライディングウィンドウプロトコルについて話します。これは TCP プロトコルのアプリケーションであり、ネットワークデータ転送中に輻輳を回避するためのフロー制御に使用されます。

TCP ヘッダーには、16 ビットのウィンドウサイズを表す win というフィールドがあります。これは、ローカル TCP 受信バッファが収容できるデータのバイト数を相手に伝え、相手側がデータの送信速度を制御できるようにすることで、フロー制御の目的を達成します。

TCP のスライディングウィンドウは、ある瞬間のウィンドウサイズが固定されたスライディングウィンドウであり、ネットワークトラフィックなどの要因が変化するとウィンドウサイズも変化します。アルゴリズムのスライディングウィンドウは、ウィンドウ (キュー/配列) を維持し、それを連続的にスライドさせて、答えを更新するという点で、多少似ています。スライディングウィンドウとは、ある種の問題を解決する方法のことです。ある種の問題は、配列上の 2 つのポインターを同じ方向に移動することによって解決されます。

スライディングウィンドウアルゴリズムの例

アルゴリズムの問題を見てみましょう。整数配列が与えられた場合、長さ k の連続するサブ配列の最大合計を計算します。

入力: arr[] = {100,200,300,400} k = 2 
 
出力: 700 
 
説明: 300 + 400 = 700

この質問を見ると、すぐに力ずくで解決する方法を考えますが、2 つの for で十分です。

公共  int maxSum( int [] arry, int k) {
整数 サイズ= 配列の長さ;
整数最大合計 = 0; 
 
 ( int i = 0; i <サイズ- k + 1; i++) {
 int現在の合計 = 0;
 ( int j = 0; j < k; j++)の場合{
              現在の合計 = 現在の合計 + 配列[i + j];
          } 
 
          maxSum = Math.max (現在の合計、最大合計);
      } 
 
 maxSumを返します。
  }

ブルートフォース法では 2 つのネストされた for ループが使用され、時間の計算量は O(k*n) と理想的ではありませんが、スライディングウィンドウアルゴリズムではネストされたループの問題を解決し、時間の計算量を効果的に削減できます。

スライディングウィンドウは、ウィンドウを維持し、継続的にスライドさせてから、答えを更新するためです。スライディングウィンドウアルゴリズムを使用して、次の手順を実行します。

k=2のとき、

長さ2のウィンドウを維持し、最初のウィンドウ値の合計を初期化して保存することができます。
その後、ウィンドウは右にスライドし続け、スライドの過程で保存された最大値と比較され、答えが更新されます。
ウィンドウは右端までスライドするまで終了しません。

k=3の場合も同様

長さ3のウィンドウを維持し、最初のウィンドウ値の合計を初期化して保存することができます。
その後、ウィンドウは右にスライドし続け、スライドの過程で保存された最大値と比較され、答えが更新されます。
ウィンドウは右端までスライドするまで終了しません。

したがって、次のようなコードを記述できます。

公共  int maxSum1( int [] arry, int k) {
整数 サイズ= arry.length; 
 
     (サイズ<k)の場合{
 -1 を返します。
     } 
 
     // 最初のウィンドウ値の合計を初期化します
整数最大合計 = 0;
 ( int i = 0; i < k; i++) {
         最大合計 = 最大合計 + arry[i];
     } 
 
整数 合計= 最大合計;
 ( int i = k; i <サイズ; i++) {
合計=合計+ 配列[i] - 配列[i - k];
         maxSum = Math.max (maxSum、合計);
     } 
 
 maxSumを返します。
 }

スライディングウィンドウを使用すると、時間の計算量は O(n) のみになります。

スライディングウィンドウはどのような問題を解決できますか?

スライディングウィンドウを使用して解決できる LeetCode の問題はどれですか?

一般に、最小カバー部分文字列、最小の長さを持つサブ配列などの部分文字列の問題はすべて、スライディングウィンドウアルゴリズムを使用して解決できます。より典型的なスライディングウィンドウの質問は次のとおりです。

重複文字のない最長の部分文字列
最小被覆部分文字列
単語のすべての部分文字列を連結する
最大2つの異なる文字を含む最長の部分文字列
最小の長さを持つサブ配列
スライディングウィンドウの最大値
弦の配置
最小ウィンドウサブシーケンス

これらはすべて Leetcode からのオリジナルの質問です。Leetcode の公式 Web サイトにアクセスして、質問の雰囲気をつかんでください。

スライディングウィンドウフレームルーチン

スライディングウィンドウの一般的な論理フレームワーク、疑似コードは次のとおりです。

整数 左= 0、右= 0;
 while (右< s.size ()) {
  // ウィンドウを大きくする
  window.add (s[右]);
右++; 
   
  while (ウィンドウを縮小する必要がある){
    // ウィンドウを縮小する
    window.remove (s[左]);
左++;
  }
 }

基本的なプロセスは次のとおりです。

まず最初に、元の文字列の長さを取得します。
次にウィンドウ（配列、ハッシュ、キュー）を維持します
ウィンドウは段階的に右に拡大します
ウィンドウが拡大して右にスライドしているときに、左側を縮小する必要があるかどうかを判断する必要があります。
最終比較更新回答

このフレームワークを使用して、実際の LeetCode の質問を解決してみましょう。

タイトル: 文字列 s が与えられた場合、重複する文字を含まない最長の部分文字列の長さを計算してください。

例1:

入力: s = "abcabcbb"  
出力: 3
説明: 重複文字のない最長の部分文字列は「abc」なので、その長さは 3 です。

例2:

入力: s = "bbbbb"   
 
出力: 1 
 
説明: 重複文字のない最長の部分文字列は「b」なので、その長さは 1 です。

重複した文字があるかどうかを判断する必要があるため、ウィンドウとしてハッシュセット（HashSet）を使用します。

 int lengthOfLongestSubstring(文字列 s){
     //元の文字列の長さを取得します
int len = s.length();
     //ハッシュコレクションウィンドウを維持する
<文字>を設定します。windows = new HashSet<>();
整数 左= 0、右= 0;
整数res =0; 
 
     while(右<len){
 char c = s.charAt(右);
       //ウィンドウを右に移動する
右++; 
 
       //左のウィンドウを縮小する必要があるかどうかを判断します。すでに含まれている場合は縮小する必要があります
       while ( windows.contains (c)){
          windows.remove(s.charAt(左));
左++;
       }
       ウィンドウズ.add (c);
       // 答えを比較して更新する
       res = Math.max ( res,windows.size ());
      }
 resを返します。
 }

Leetcode ケース分析

印象を深めるために、実際の LeetCode の質問をもう一つ見てみましょう。

タイトル: 文字列 S と文字列 T が与えられます。 T 内のすべての文字を含む S の最小の部分文字列を返します。 S に T のすべての文字を含む部分文字列がない場合、空の文字列 "" が返されます。

例1:

入力: s = "ADOBECODEBANC" 、t = "ABC"   
 
出力: "BANC"

例2:

入力: s = "a" 、t = "a"   
 
出力: "a"

私たちは今でもこのフレームワークプロセスを適用しています:

 - まず、元の文字列の長さを取得します。 
 
 - 次にウィンドウ（配列、ハッシュ、キュー）を維持します
 
 - ウィンドウが段階的に右に拡大します
 
 - ウィンドウが拡大して右にスライドしているとき、左側を縮小する必要があるかどうかを判断する必要があります。 
 
 - 前回の比較更新された回答

元の文字列の長さを取得します。

これは比較的簡単です。元の質問では、文字列 S をトラバースするために左ポインタと右ポインタがまだ必要だからです。

 int len = S.length();

次にウィンドウ（配列、ハッシュ、キュー）を維持し、右にシフトし、左に減らす

まず、長さが 0 の最小ウィンドウを定義します。ウィンドウを定義するときは、ウィンドウがいつ右に移動するのか、いつ左に縮小するのか、そしてどのように比較して答えを更新するのかを考える必要があります。

最小のウィンドウを右にシフトできるのはいつですか? 質問では T のすべての部分文字列をカバーする必要があるため、ウィンドウは T のすべての文字が含まれるまで先頭で右にシフトできます。

明らかに、ウィンドウ文字列 ADOBEC は、T のすべての文字をカバーする S の最初の部分文字列です。ただし、私たちが探しているのは最小の部分文字列であり、ADOBEC が最小のものではない可能性があります。なぜなら：

1. 現在のウィンドウには、タイトル条件を満たす小さなサブウィンドウ文字列が含まれている可能性があります。（左側は縮小可能）
2. ウィンドウがスライドしていない領域に、条件を満たす小さな文字列が含まれている可能性があります。（ウィンドウは右に移動し続けることができます）

条件を満たす最初のウィンドウ文字列 ADOBEC を見つけた後、より小さな子ウィンドウ文字列を探します。我々はできる：

1. 左側を縮小します。縮小されたウィンドウにまだ T のすべての文字が含まれている場合、現在のウィンドウは最小の部分文字列である可能性があります。それを格納し（スライディングウィンドウフレームの更新された回答と同様に）、左からウィンドウを縮小し続けます。
2. ウィンドウを縮小しても T を含むすべての文字が収まらない場合は、ウィンドウの左側の縮小を停止し、ウィンドウを右側に拡大することができます。

ウィンドウは最初に左側に縮小され、次に右側に移動し、条件を満たすウィンドウが保存されます

上記の手順を繰り返し、条件を満たすウィンドウを保存し、比較して最小の部分文字列を取得します。条件を満たす最小の部分文字列はBANCである

この問題の難しいところは、実際には S の部分文字列に T が含まれているかどうかをどうやって判断するかということです。コードを見てみましょう。

クラスソリューション{
パブリック文字列minWindow(文字列s、文字列t) {
        s.length() == 0 || s.length() < t.length() の場合 {
戻る  "" ;
        } 
 
 int sLen = s.length();
        Map<文字、整数> lookup = new HashMap<>(); 
          
 ( int i = 0; i < sLen; i++) {
            lookup.put(s.charAt(i), 0);
        } 
 
 ( int i = 0; i < t.length(); i++) {
文字c = t.charAt(i);
            （lookup.containsKey(c)）の場合{
                lookup.put(c, lookup.get(c) + 1);
            }それ以外{
戻る  "" ;
            }
        } 
 
整数 左= 0;
整数 右= 0;
 int minLen = Integer.MAX_VALUE ;
 int tCount = t.length();
        文字列結果 = "" ;
        （右の長さがsLen未満の場合）
 char c = s.charAt(右);
            lookup.get(c) > 0 の場合、tCount --;  
            lookup.put(c, lookup.get(c) - 1);
            //ウィンドウを右に移動する
右++; 
             
            //すでにTの文字がすべて含まれています
            (tCount == 0) の間 {
                // 答えを比較して更新する
                （最小長さ＞右-左）の場合{
                    minLen =右-左;
                    結果 = s.substring (左、右);
                }
 char c2 = s.charAt(左);
                lookup.get(c2) == 0 の場合、tCount++;
                lookup.put(c2, lookup.get(c2) + 1);
                // ウィンドウを左から縮小する
左++;
            }
        }
結果を返します。
    }
 }