スライディングウィンドウ

序文

様々なFAangとFanangの会社の私の十字軍の数年後に(この用語は、以下の意味)、無限のインタビューループ(時には夜)、私は知識の細かいデータベースを収集した後、私はdevのコミュニティに提供したいと思います.
インタビューのプロセスは読書に飽きたけど、まだゲームの一部なので、将来の参考になるようにソートすることは、私にとってこのすべてを書くためのもう一つの正当な理由です.
それで、インタビュー・プロセス(それについて、後で受け取られる申し出についての詳細)に行かないでください.インタビュー中に遭遇した様々なコーディング問題を発表しようと思います.

スライディングウィンドウ

導入

ここでは、おそらく最も人気のある退屈なものに行くが、まだかなりトリッキー!
スライドウィンドウアルゴリズムは、一般的に、配列内の隣接するシーケンス内のmax、min、またはその他のターゲット値を探す問題に使用されます.特定の条件を正確に満たす何かの最も長いシーケンスまたは最短シーケンスのように、それはしばしば最適の何らかの種類です.

識別方法

この問題は、配列や文字列のような順序で反復できるデータ構造を含みます.

あなたはその配列/文字列のいくつかのサブ範囲を探しています.

そこに実行される明らかなナイーブまたはブルートフォースソリューションがありますO(N²) , O(2^N) または他の大きな時間の複雑さ.

しかし、あなたが探している最大の問題は、特定の条件を正確に満たす何かの最も長いシーケンスまたは最短シーケンスのように、しばしば最適ないくつかの種類です.
二つのポインタで解決できる問題の特徴概要は簡単です.

If a wider scope of the sliding window is valid, the narrower scope of that wider scope is valid ミュートホールド.

If a narrower scope of the sliding window is invalid, the wider scope of that narrower scope is invalid ミュートホールド.

アプローチ

ウィンドウは、あなたが「見ている」ストリング/配列の現在のセクションを表します、そして、通常、定数の形でそれとともに格納される若干の情報があります.少なくとも、それは2つのポインタを持っています.そして、1がインデックスを示している1つのウィンドウ、およびウィンドウの終わりを示している1を示します.

基本パターン:
ダイナミックな周波数マップがその場で計算されることができる単一の配列/ストリング入力による質問のために使われる基本的なパターン.
問題点:
Fruits into baskets

果物の種類の周波数マップを作成します.

インクリメンタル文字/数字の周波数を終了ポインタ.この場合、我々は特定のタイプの果物の数を増やします.

条件をチェックします.つ以上のバスケットが満たされないならば、ここで.

周波数が0ならばスタートポインタで要素を削除します.私たちはマップから空のバスケットを削除することができます.

長さまたは目標値を計算します.ここで明らかに木の数.

public static int findLength(char[] arr) {
  if (arr.length == 0) return 0;
    Map<Character, Integer> map = new HashMap<>();
  int start = 0, end = 0, len = 0;
  while (end < arr.length) {
      // adding fruit in here
      map.put(arr[end], map.getOrDefault(arr[end], 0) + 1);
      end++;
      while (map.size() > 2) {
          // removing fruit from basket
          map.put(arr[start], map.getOrDefault(arr[start], 0) - 1);
          if (map.get(arr[start]) == 0) {
              map.remove(arr[start]);
          }
          start++;
      }
      // max number of trees consumed
      len = Math.max(len, end - start);
  }
  return len;    
}

頻度マップパターンは主に2つの入力、例えば、文字列とパターンの配列を持つときに使用されます.例:
Permutation in a String
この場合、周波数マップをビルドする必要があります.
ここでは、より一般的な方法で書かれたステップので、任意の問題に適用することができるでしょう.

周波数マップを作成します.

条件入力入力周波数を計算します.

ターゲットカウントを初期化します.

終了ポインタを持つ数字/数の減少.

周波数マップの残りの異なる値のカウントを確認します.

コンディションチェック.

開始ポインタを持つ文字/数字の周波数をインクリメントします.

スタートポインタの値が周波数マップの1に等しいなら→ インクリメントカウンター.

周波数マップで

boolean findPermutation(String str, String pattern) {
    if (str == null || pattern == null) return false;
    Map<Character, Integer> map = new HashMap<>();
    for (char c : pattern.toCharArray()) {
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    int start = 0, end = 0, count = map.size();
    while (end < str.length()) {
        char endChar = str.charAt(end++);
        if (map.containsKey(endChar) && count >= 0) {
            map.put(endChar, map.get(endChar) - 1);
            if (map.get(endChar) == 0) {
                count--;
            }
        }
        while (count == 0) {
            if (end - start == pattern.length()) {
                return true;
            }
            char startChar = str.charAt(start++);
            if (map.containsKey(startChar)) {
                map.put(startChar, map.get(startChar) + 1);
                if (map.get(startChar) == 1) {
                    count++;
                }
            }
        }
    }
    return false;
}

k個の異なる文字列を持つサブ配列の数
leetcodeで同じ問題を見つけませんでした.しかし、タイトルから実現するのは簡単です:あなたは配列を与えられます、そして、ゴールはK(与えられた数)で異なった文字のサブ配列の数を見つけることです.
入力:S =
出力: 7
説明:[ 1 , 2 ], [ 1 , 2 , 1 ], [ 1 , 2 , 1 , 2 ], [ 2 , 1 , 2 ] , [ 2 , 3 , ] , [ 2 , 3 ]
これは多くのトリッキーであり、いくつかの小さなトリックを適用する必要があります.

トリックはatMostK(A, K) - atMostK(A, K - 1) .
従って、k個のサブアレイの数はサブアレイの数であると言える
K - 1で最も多くのK個の異なった数のサブアレイの最も多くのK.
スライディングウィンドウでは、すべてのウィンドウをkまで探索します.

count += end - start ウィンドウ内のすべてのサブアレイを与えます.番号を追加するたびに、WindowRangeサイズのサブアレイを追加します.
[ 1 , 2 , 3 ]→ ［1］1,2,2,2,1,2,3［3］−ウインドワードサイズのサブアレイを毎回サブアレイする.

 public int subarraysWithKDistinct(int[] A, int K) {
        **return atMostK(A, K) - atMostK(A, K - 1);**
    }
    int atMostK(int[] arr, int k) {
        if (k == 0) return 0;
        Map<Integer, Integer> map = new HashMap<>();
        int start = 0, end = 0, count = 0;
        while (end < arr.length) {
            map.put(arr[end], map.getOrDefault(arr[end], 0) + 1);
            end++;
            while (map.size() > k) {
                map.put(arr[start], map.getOrDefault(arr[start], 0) - 1);
                if (map.get(arr[start]) == 0) {
                    map.remove(arr[start]);
                }
                start++;
            }
            count += end - start; // trick here : we can add all subarrays between end and start
        }
        return count;
    }

複雑さ

ほとんどの時間では、ウィンドウの問題を解決するO(n)の時間とO(1)の空間の複雑さで解決することができます.
追加入力なしで基本的なアプローチのために:o(n)時間とo(1)スペース.
周波数マップアプローチ:O(n)またはO(n + m)の時間とO(m)空間は、追加の入力データの量です.