---

1545. 找出第 N 个二进制字符串中的第 K 位

• 标签：递归、字符串、模拟
• 难度：中等

题目链接

• 1545. 找出第 N 个二进制字符串中的第 K 位 - 力扣

题目大意

描述：定义一个字符串序列 $S_1, S_2, S_3, \dots$，其中：

• $S_1 = "0"$。
• 对于 $i > 1$，$S_i = S_{i-1} + "1" + reverse(invert(S_{i-1}))$。
  • $invert$：翻转每个字符（$0 \to 1$，$1 \to 0$）。
  • $reverse$：将字符串反转。

给定 $n$ 和 $k$（$1$-based）。

要求：返回 $S_n$ 中第 $k$ 位的字符。

说明：

• $1 \le n \le 20$。
• $1 \le k \le 2^n - 1$。

示例：

• 示例 1：

输入：n = 3, k = 1
输出："0"
解释：S3 为 "0111001"，其第 1 位为 "0" 。

• 示例 2：

输入：n = 4, k = 11
输出："1"
解释：S4 为 "011100110110001"，其第 11 位为 "1" 。

解题思路

思路 1：递归 + 分类讨论

1. 核心思想

$S_n$ 的长度为 $2^n - 1$。其结构为：

$$S_n = S_{n-1} + "1" + reverse(invert(S_{n-1}))$$

记 $len = 2^{n-1} - 1$（$S_{n-1}$ 的长度）。$S_n$ 的长度为 $2 \times len + 1 = 2^n - 1$。

对于第 $k$ 位（$1$-based）：

• 如果 $k == len + 1$：中间位，结果为 $1$。
• 如果 $k \le len$：在左半部分，递归到 $S_{n-1}$ 中找第 $k$ 位。
• 如果 $k > len + 1$：在右半部分，对应 $S_{n-1}$ 中的第 $2 \times len + 2 - k$ 位（反转后的映射），但需要翻转（因为经过了 $invert$）。

2. 具体步骤

第 1 步：基础情况 $n = 1$，$S_1 = "0"$，返回 "0"。

第 2 步：计算 $len = 2^{n-1} - 1$。

第 3 步：分类讨论：

• $k == len + 1$：返回 "1"。
• $k \le len$：递归 $findKthBit(n-1, k)$。
• $k > len + 1$：递归 $findKthBit(n-1, 2 \times len + 2 - k)$，然后翻转（$0 \to 1$，$1 \to 0$）。

3. 正确性证明

$S_n = S_{n-1} + "1" + reverse(invert(S_{n-1}))$。

设 $S_{n-1}$ 的长度为 $len$。

右半部分 $reverse(invert(S_{n-1}))$ 的第 $i$ 位（$1$-based）对应 $S_{n-1}$ 的第 $len - i + 1$ 位取反。

所以 $S_n$ 的第 $k$ 位（$k > len+1$）对应 $S_{n-1}$ 的索引为 $len - (k - len - 2)$ = $2 \times len + 2 - k$，取反。

4. 举例说明

以 $n = 3, k = 5$ 为例：

$S_1 = "0"$
$S_2 = "0" + "1" + invert("0") \text{反转} = "011"$（$invert("0")="1"$，反转后还是 "1"）
$S_3 = "011" + "1" + reverse(invert("011")) = "011" + "1" + "100" = "0111100"$

$S_3$ 长度 $7$，$k=5$：

• $len = 2^{2} - 1 = 3$
• $k > len+1=4$，进入右半部分。
• 递归 $n=2$，找第 $2 \times 3 + 2 - 5 = 3$ 位。
• $n=2$，$len = 2^{1} - 1 = 1$，$S_2 = "011"$。
• $k = 3 > len+1=2$，进入右半部分。
• 递归 $n=1$，找第 $2 \times 1 + 2 - 3 = 1$ 位。
• $S_1 = "0"$，第 $1$ 位为 $0$。
• 回溯：$n=2$ 处翻转，$0 \to 1$。
• $n=3$ 处再翻转，$1 \to 0$。

结果第 $5$ 位为 $0$。

思路 1：代码

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        if n == 1:
            return "0"
        length = (1 << n) - 1          # 2^n - 1
        mid = (length + 1) // 2        # 中间位置
        if k == mid:
            return "1"
        elif k < mid:
            return self.findKthBit(n - 1, k)
        else:
            # 右半部分：对应左半部分的对称位置取反
            res = self.findKthBit(n - 1, length - k + 1)
            return "1" if res == "0" else "0"

思路 1：复杂度分析

• 时间复杂度：$O(n)$，每次递归 $n$ 减 $1$。
• 空间复杂度：$O(n)$，递归栈深度。

---

思路 2：迭代

也可以用迭代代替递归，从 $n$ 开始向下直到 $1$，记录翻转次数。

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        flip = 0
        while n > 1:
            length = (1 << n) - 1
            mid = (length + 1) // 2
            if k == mid:
                return "1" if flip % 2 == 0 else "0"
            elif k > mid:
                k = length - k + 1
                flip += 1
            n -= 1
        return "0" if flip % 2 == 0 else "1"