目标
给你两个正整数 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 长度范围以内。
示例 1：
输入：n = 3, k = 1
输出："0"
解释：S3 为 "0111001"，其第 1 位为 "0" 。示例 2：
输入：n = 4, k = 11
输出："1"
解释：S4 为 "011100110110001"，其第 11 位为 "1" 。示例 3：
输入：n = 1, k = 1
输出："0"示例 4：
输入：n = 2, k = 3
输出："1"说明：
- 1 <= n <= 20
- 1 <= k <= 2^n - 1
思路
长度为 n 的二进制字符串的递推公式为 S_1 = 0, S_i = S_(i-1) + "1" + reverse(invert(S_(i-1)))，返回 S_n 的 第 k 位 字符，k 从 1 开始。
简单的做法是根据题意模拟，改写一下递推公式的下标，从 i = 0 开始，已知递推公式 s[0] = '0', s[i] = s[i - 1] + '1' + invertAndReverse(s[i - 1])，求 s[n - 1].charAt(k - 1)。
一个更优的做法是递归。s[i] 的长度 len[i] = 2 * len[i - 1] + 1 => len[i] + 1 = 2 (len[i - 1] + 1)，len[i] + 1 是一个首项为 2，公比为 2 的等比数列，第 i 项长度为 2^i - 1。可以将它划分成三部分，注意这里下标从 1 开始：
1 ~ 2^(i - 1) - 1即s[i - 1]，如果k在左半边，问题变为s[i - 1]的第k个字符2^(i - 1)值是1，直接返回2^(i - 1) + 1 ~ 2^i - 1即invertAndReverse(s[i - 1])，如果k在右半边，问题变为invertAndReverse(s[i - 1])的第k - 2^(i - 1)个字符，也是invert(s[i - 1])的第2^(i - 1) - k + 2^(i - 1) = 2^i - k个字符。
代码
/**
* @date 2026-03-03 14:13
*/
public class FindKthBit1545 {
public char findKthBit(int n, int k) {
StringBuilder[] s = new StringBuilder[n];
Arrays.setAll(s, x -> new StringBuilder());
s[0].append('0');
for (int i = 1; i < n; i++) {
s[i].append(s[i - 1]).append('1').append(invertAndReverse(s[i - 1]));
}
return s[n - 1].charAt(k - 1);
}
public StringBuilder invertAndReverse(StringBuilder origin) {
StringBuilder res = new StringBuilder();
for (int i = 0; i < origin.length(); i++) {
if (origin.charAt(i) == '0') {
res.append('1');
} else {
res.append('0');
}
}
return res.reverse();
}
}
性能
