尋找第 N 個二進位字串中的第 K 位

1545。尋找第 N 個二進位字串中的第 K 位元

難度：中

主題：字串、遞歸、模擬

給定兩個正整數 n 和 k，二進位字串 S_n 的形成如下：

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

其中表示串聯操作，reverse(x) 傳回反轉後的字串 x，invert(x) 將 x 中的所有位元反轉（0 變為 1，1 變為 0）。

例如，上述序列中的前四個字串是：

• 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" 反轉(反轉(S_i-1))
   • 這表示S_i由三個部分組成：
     • 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 並映射kkk 直到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，_SiSi
為「0」 ，因此任何
• k
  的唯一可能值為「0」。
  • 遞迴步驟： 計算中間索引^mid，即
  2
  • n-1。
  如果
  • k 符合中間索引，則傳回「1」。 如果k小於mid，則第k，則第_k，則第
  k
  • 位位於前半部分，因此我們遞歸地找到Sn-1k
  位>.

如果

k

• 大於mid，我們在反向反轉的後半部中找到相應的位元並將其翻轉。 複雜度分析：
• 時間複雜度：O(n)，因為每次遞歸呼叫都會將

n

減少1。

1. 空間複雜度：O(n) 遞歸呼叫堆疊。 演練範例：

   輸入：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' = 2k' ^{= 2} - 11 = 5
   • . 在S3 中找到
   k = 5
，即“0”，然後翻轉它到“1”。

透過利用遞歸和字串構造的屬性，該解決方案避免了產生整個字串，即使對於較大的

n

. 也能保持高效。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給

存儲庫

一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

• 如果您想要更多類似的有用內容，請隨時關注我：
• 領英

GitHub

以上是尋找第 N 個二進位字串中的第 K 位的詳細內容。更多資訊請關注PHP中文網其他相關文章！