查找第 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 并映射 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 上给

存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是查找第 N 个二进制字符串中的第 K 位的详细内容。更多信息请关注PHP中文网其他相关文章！