题目

给你两个正整数 n 和 k，二进制字符串 Sn 的形成规则如下：

S1 = "0" 当 i > 1 时，Si = Si-1 + "1" + reverse(invert(Si-1)) 其中 + 表示串联操作，reverse(x) 返回反转 x 后得到的字符串，而 invert(x) 则会翻转 x 中的每一位（0 变为 1，而 1 变为 0）。

例如，符合上述描述的序列的前 4 个字符串依次是：

S1 = "0" S2 = "011" S3 = "0111001" S4 = "011100110110001" 请你返回 Sn 的 第 k 位字符 ，题目数据保证 k 一定在 Sn 长度范围以内。

题解

首先我尝试了暴力解法，直接生成 Sn，但是发现当 n 比较大时，Sn 的长度会非常长，导致内存溢出。

/**
 * @param {number} n
 * @param {number} k
 * @return {character}
 */
var findKthBit = function (n, k) {
  var reverseR = function (input) {
    return input
      .split("") // 拆分成数组 ["0", "1", "1", "1", "0"]
      .map((char) => char ^ 1) // 翻转每一位: [1, 0, 0, 0, 1]
      .reverse() // 反转数组顺序: [1, 0, 0, 0, 1]
      .join(""); // 拼回字符串 "10001"
  };
  let S = "0";
  for (let i = 1; i < n; i++) {
    S = S + "1" + reverseR(S);
  }
  return S[k - 1];
};

然后我尝试了数学翻转。观察 $S_i = S_{i-1} + "1" + \text{reverse}(\text{invert}(S_{i-1}))$：

长度规律：$|S_n| = 2^n - 1$。

• 例如 $S_1$ 长度 $2^1-1=1$，中间位是第 $1$ 位。
• $S_2$ 长度 $2^2-1=3$，中间位是第 $2$ 位。
• $S_3$ 长度 $2^3-1=7$，中间位是第 $4$ 位。

三种位置分类讨论：

• 左半部分 (k < mid)：它完全就是 $S_{n-1}$ 的副本。所以直接去问“$S_{n-1}$ 的第 $k$ 位是什么”即可。
• 正中间 ($k = mid$)：根据逻辑公式，这一位永远是 "1"。
• 右半部分 (k > mid)：这是最巧妙的地方。右边部分是 $S_{n-1}$ 取反再反转。

因为有 反转（Reverse），所以右半部分的第 1 个字符对应左半部分的最后一个，依次类推。

对应关系公式：$S_n[k] = \text{invert}(S_{n-1}[2^n - k])$。

比如在 $S_3$（长度 7）中找第 6 位，它对应 $S_2$ 的第 $2^3 - 6 = 2$ 位的结果再取反。

var findKthBit = function (n, k) {
  let flip = false; // 记录需要取反的次数
  while (n > 1) {
    let mid = 1 << (n - 1); // 2^(n-1)
    if (k === mid) {
      // 中间位固定为 1
      let res = 1;
      return (flip ? res ^ 1 : res).toString();
    } else if (k > mid) {
      // 如果在右侧，镜像到左侧，并增加一次取反
      k = 2 * mid - k;
      flip = !flip;
    }
    // 如果在左侧，直接继续看 n-1
    n--;
  }
  // 最终回到 S1，S1 是 "0"
  let res = 0;
  return (flip ? res ^ 1 : res).toString();
};

mid 为什么是 $2^{n-1}$？

我们通过计算 $S_n$ 的总长度就能推导出中心点（mid）的位置。

计算 $S_n$ 的总长度：设 $L_n$ 为第 $n$ 个字符串 $S_n$ 的长度。根据题目规则：

• $S_1 = "0"$，所以 $L_1 = 1$
• $S_n = S_{n-1} + "1" + \text{修改后的 } S_{n-1}$

那么长度关系式为： $L_n = L_{n-1} (\text{左半部分}) + 1 (\text{中间位}) + L_{n-1} (\text{右半部分})$ 即：$L_n = 2 \times L_{n-1} + 1$

我们可以列举一下：

• $L_1 = 1$
• $L_2 = 2 \times 1 + 1 = 3$
• $L_3 = 2 \times 3 + 1 = 7$
• $L_4 = 2 \times 7 + 1 = 15$

规律：$L_n = 2^n - 1$

2. 为什么我们要这样找？

这就好比你在一个无限折叠的纸带上找特定的点：

• 原来的做法（模拟）：先把一张白纸折 20 次，把它变成一个超级长的纸带，然后再从头开始数到第 $k$ 个点。
• 现在的做法（回溯/迭代）：看着这张已经“折好”的纸（$S_n$），问：这个 $k$ 点是在折痕的左边还是右边？
  • 如果它在折痕右边，你就把它“翻”回左边（镜像转换），并记下它被翻过了一次（flip = !flip）。
  • 如果它在折痕左边，你就直接看左边。
  • 现在纸变小了一半（n--），你重复这个过程，直到你摸到了那道“折痕”（k === mid）或者纸缩小到不能再缩（n=1）。

3. 如果在右侧，且S[k]=0，是不是翻转过去说明S[k]=1了

为什么“翻转过去”就是 1？

根据题目，$S_i$ 的右半部分是：$\text{reverse}(\text{invert}(S_{i-1}))$。 这里有两个动作：

• 取反 (invert)：这一步让 $0 \to 1$，$1 \to 0$。
• 反转 (reverse)：这一步让位置左右颠倒。

所以，如果在右半部分看到了一个 0，顺着这两步推回去：

• 因为“取反”过：说明它在被取反之前是 1。
• 因为“反转”过：说明它对应的位置在左半边的对称点。

Involution Hell© 2026 byCommunityunderCC BY-NC-SA 4.0