N 番目のバイナリ文字列の K 番目のビットを検索する

1545年。 N 番目のバイナリ文字列の K 番目のビットを検索

難易度: 中

トピック: 文字列、再帰、シミュレーション

2 つの正の整数 n と k が与えられると、バイナリ文字列 S_n は次のように形成されます。

• S₁ = "0"
• S_i = S_{i - 1} "1" reverse(invert(S_{i - 1})) for i > 1

ここで、 は連結演算を示します。reverse(x) は反転した文字列 x を返し、invert(x) は x のすべてのビットを反転します (0 は 1 に、1 は 0 に変化します)。

たとえば、上記のシーケンスの最初の 4 つの文字列は次のとおりです。

• S₁ = "0"
• S₂ = "011"
• S₃ = "0111001"
• S₄ = "011100110110001"

Sn の k _番目 ビットを 返します。 k が指定された n に対して有効であることが保証されます。

例 1:

• 入力: n = 3、k = 1
• 出力: "0"
• 説明: S₃ は、「0111001」です。 1^番目ビットは「0」です。

例 2:

• 入力: n = 4、k = 11
• 出力: "1"
• 説明: S₄ は、「011100110110001」です。 11^番目ビットは「1」です。

例 3:

• 入力: n = 3、k = 2
• 出力: "0"

制約:

• 1
• 1 n - 1

ヒント:

1. n が小さいので、S1 から Sn を構築するプロセスを単純にシミュレートできます。

解決策:

各バイナリ文字列 S_n を生成するために使用される再帰プロセスを理解し、これを使用して全体を構築せずに k 番目のビットを決定する必要があります。文字列。

アプローチ：

1. 再帰的な文字列の構築:

   • S₁ = "0".
   • 私にとって> 1:
     • S_i は次のように構築されます。 S_i = S_i-1 "1" reverse(invert(S_i-1))
   • これは、S_i が 3 つの部分で構成されていることを意味します。
     • S_i-1 (オリジナル部分)
     • 「1」(中間ビット)
     • reverse(invert(S_i-1)) (変換された部分)

2. 主な所見:

   • S_i の長さは 2^i-1 です。
   • 中間ビット (Sⁱ2i-1) > は常に「1」です。
   • k が前半にある場合、それは Si-1 に収まります。
   • k がちょうど真ん中の位置の場合、答えは「1」です。
   • kが後半にあれば反転部分に相当します。

3. 反転と反転:

   後半のビットを決定するには、以下を使用して
   • k を前半の対応する位置にマッピングします。 k' = 2i ^{- k}
   元の半分のこの位置のビットは反転されているため、結果を反転する必要があります。

4. 再帰的解決策:

   • n を削減し、kk 番目のビットを再帰的に決定します🎜> n = 1まで。
このソリューションを PHP で実装してみましょう:

1545。 N 番目のバイナリ文字列の K 番目のビットを検索

説明：

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

基本ケース
• : n = 1の場合、Siは「0」ですしたがって、k の唯一の値は "0" です。
再帰的なステップ
• : 中間インデックス
  • mid、つまり 2n-1 を計算します。
  • k が中央のインデックスと一致する場合、「1」を返します。
  • k が mid より小さい場合、k 番目ビットは前半にあるため、Sn-1k _{番目のビットを再帰的に見つけます。 >.}
  k
  • が mid より大きい場合、逆反転された後半で対応するビットを見つけて反転します。
  複雑さの分析:

時間計算量

:
• O(n)。これは、再帰呼び出しごとに n が 1 ずつ減少するためです。 空間複雑度
: 再帰呼び出しスタックの
• O(n)。 チュートリアルの例:

入力
1. :

   n = 3、k = 1

   • S₃ = "0111001"
   • k = 1 は前半にあるため、Sk = 1 を探します。 >2.
   • S2 = "011" 、k = 1 「0」に対応します。

2. 入力: n = 4 、k = 11

   • S4 = "011100110110001"
   • S4 の中間インデックスは 8 です。
   • k = 11は後半に落ちます。
   • k = 11 を前半の対応するビットにマップします: k' = 2 4 ^{- 11 = 5}.
   • S3 で _{k = 5} (「0」) を見つけて反転します。 「1」にします。

このソリューションは、再帰と文字列構築のプロパティを活用することで、文字列全体の生成を回避し、より大きな

n に対しても効率的になります。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で

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

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

• LinkedIn
• GitHub

以上がN 番目のバイナリ文字列の K 番目のビットを検索するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。