左と右から各文字の K を取得します

2516。左と右から各文字の K を取り出します

難易度: 中

トピック: ハッシュ テーブル、文字列、スライディング ウィンドウ

文字「a」、「b」、「c」で構成される文字列 s と、負でない整数 k が与えられます。 1 分ごとに、s の 左端 文字、または s の 右端 文字のいずれかを取得できます。

各文字の 少なくとも k を取得するのに必要な 最小 分数を 返します。各文字の k を取得できない場合は -1 を返します。キャラクター.

例 1:

• 入力: s = "aabaaaacaabc"、k = 2
• 出力: 8
• 説明: s の左から 3 文字を取ります。これで、「a」文字が 2 つと「b」文字が 1 つになりました。
  • s の右から 5 文字を取ります。これで、「a」文字が 4 つ、「b」文字が 2 つ、「c」文字が 2 つになりました。
  • 合計 3 5 = 8 分が必要です。
  • 必要な最小時間は 8 分であることが証明できます。

例 2:

• 入力: s = "a"、k = 1
• 出力: -1
• 説明: 'b' または 'c' を 1 つ取ることはできないため、-1 を返します。

制約:

• 1 5
• s は、文字「a」、「b」、および「c」のみで構成されます。
• 0

ヒント:

1. 各文字の頻度を数えて、それが可能かどうかを確認することから始めます。
2. 左側から x 文字を取得する場合、右側から取得する必要がある文字の最小数は何ですか? 0 ≤ x ≤ s.length.
の範囲内の x のすべての値についてこれを求めます。
3. 同じ情報を複数回計算することを避けるために、2 ポインターのアプローチを使用します。

解決策:

2 つのポインターを使用したスライディング ウィンドウ手法を使用して、文字列の左側と右側の両方から少なくとも k 個の各文字 ('a'、'b'、'c') を取得するのに必要な最小時間を見つけることができます。文字列。

問題の内訳:

• 「a」、「b」、「c」のみを含む文字列 s が与えられています。
• 文字列の左端または右端の文字から、各文字が少なくとも k 回出現する必要があります。
• これを達成するために必要な最小分数を決定するか、それが不可能な場合は -1 を返す必要があります。

アプローチ：

1. 初期チェック:

   • k == 0 の場合、文字は必要ないため、直接 0 を返すことができます。
   • k が文字列内の文字の出現数を超えた場合は、すぐに -1 を返します。

2. 頻度カウント:

   • 各文字の k 個を収集できることを確認するには、文字列 s に「a」、「b」、「c」が何回出現するかをカウントする必要があります。

3. スライディング ウィンドウ テクニック:

   • 2 つのポインター (左と右) を使用してスライディング ウィンドウ アプローチを使用します。
   • 2 つのポインターを維持し、文字列の両端からスライドさせて、必要な文字を集めます。
   • 左から取得する文字数ごとに、要件を満たすために右から取得する必要がある最小文字数を計算します。

4. 最適化:

   • ウィンドウごとに文字数を繰り返し再計算する代わりに、ウィンドウを拡大または縮小するときに文字数を追跡できます。

このソリューションを PHP で実装してみましょう: 2516。左と右から各文字の K を取り出します

<?php
/**
 * @param String $s
 * @param Integer $k
 * @return Integer
 */
function takeCharacters($s, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
echo takeCharacters("aabaaaacaabc", 2);  // Output: 8

// Example 2
echo takeCharacters("a", 1);  // Output: -1
?>

説明：

1. 初期セットアップ:

   • 文字列全体で「a」、「b」、および「c」の出現をカウントし、各文字を少なくとも k 個収集できることを確認します。
   • 文字数が k 未満の場合は、-1 を返します。

2. スライディング ウィンドウ:

   • 2 つのポインター (左右) を使用して、両端からスライディング ウィンドウを作成します。
   • 右ポインタを移動してウィンドウを拡大し、見つかった文字の数を増やします。
   • 現在のウィンドウに少なくとも k 個の各文字があれば、分数 (文字の取得) を最小限に抑えるためにウィンドウを左から縮小しようとします。

3. 時間を最小限に抑える:

   • すべてのタイプの k 個の文字を収集するたびにウィンドウのサイズを比較することで、必要な最小の分数を追跡します。

時間計算量:

• 文字数のカウントには最初は O(n) かかります。
• 左右のポインタの両方が文字列上を 1 回移動するため、スライディング ウィンドウの操作には O(n) かかります。
• 全体の時間計算量は O(n) です。

エッジケース:

• k == 0 の場合、0 を返します。
• 各文字の k を取ることが不可能な場合は、-1 を返します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が左と右から各文字の K を取得しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。