企业官网建设流程全解析

LeetCode 1545. 找出第 N 个二进制字符串中的第 K 位，这道题我刷第一眼觉得简单，细看才发现它把“模拟”、“递归”、“数学映射”三个层次全串在了一起。题目给了一个二进制字符串序列 Sn，规则很直白：S1 = "0"，从 S2 开始，每个新串都是“上一个串 + 一个固定字符 1 + 上一个串反转后再取反的结果”。要求回答第 n 个字符串里的第 k 位是 0 还是 1。今天我把两条主流解法完整拆开讲，从直接构造字符串的模拟思路，到基于位置对称映射的递归（数学）思路，再把迭代写法、复杂度对比和典型坑点一次说清楚，适合正在刷 LeetCode 热题、想系统搞懂字符串构造类问题的朋友。

我先说结论：这道题 n 最大只有 20，模拟完全跑得动；但递归（数学）解法可以把时间从 O(2^n) 压到 O(n)，而且推导过程本身才是真正值得学的东西。两种解法我都写了可运行代码，你照着抄也能过，但更建议把推导逻辑看明白，因为“对称反转取反”这种结构在很多题里都会出现。

1. 题目拆解：先搞清 Sn 是怎么长出来的

1.1 Sn 构造规则与手动推导

题目定义的构造规则是：

• S1 = "0"
• 对 i >= 2，Si = S(i-1) + "1" + reverse(invert(S(i-1)))

其中 invert 表示按位取反，也就是 0 变成 1，1 变成 0；reverse 表示把字符串整体倒序。

手动推一遍就清楚了。S1 是 "0"，所以 S2 = "0" + "1" + reverse(invert("0")) = "0" + "1" + reverse("1") = "011"。

继续推 S3：S2 = "011"，invert 后是 "100"，reverse 后还是 "001"，所以 S3 = "011" + "1" + "001" = "0111001"。

S4 同理，S3 = "0111001"，invert 后是 "1000110"，reverse 后是 "0110001"，所以 S4 = "0111001" + "1" + "0110001" = "011100110110001"。

注意一个细节：“先反转再取反”和“先取反再反转”结果完全一样，因为取反是对每个字符独立操作，反转只改变顺序，两者可以交换。这一点在写模拟代码时很有用，你可以按自己顺手的顺序来。

1.2 三个必须记住的结构特征

构造规则看懂了，还要总结出三个特征，它们是递归解法的地基。

第一，长度公式。len(1) = 1，而每个新串等于两个旧串加一个字符，所以 len(i) = 2 * len(i-1) + 1。解这个递推能得到闭式公式 len(n) = 2^n - 1。比如 S4 长度是 2^4 - 1 = 15，和上面推出来的一致。

第二，中位固定是 1。注意每次构造都是把上一个串放在左边，中间拼一个固定字符 "1"，所以第 2^(n-1) 位（从 1 开始计数）一定是 "1"。这是递归里一个可以直接返回的边界分支。

第三，左右两边关于中位镜像且取反。因为右边部分就是左边部分经过 reverse 和 invert 得到的，换句话说，Sn 右侧第 i 个字符，等于左侧第 len(n) - i + 1 个字符取反。这个“对称 + 取反”关系是整个题目的题眼。

2. 方案一：直接模拟构造字符串

2.1 模拟代码与实现细节

先上最简单的思路：把 Sn 真的造出来，然后取 s[k-1]。注意 k 是从 1 开始计数的，所以数组下标要减 1。

Python 写法：

def findKthBit(n: int, k: int) -> str: s = "0" for _ in range(2, n + 1): # 先反转再取反，注意这里用的是上一轮的 s t = "".join("1" if ch == "0" else "0" for ch in reversed(s)) s = s + "1" + t return s[k - 1]

C++ 写法：

class Solution { public: char findKthBit(int n, int k) { string s = "0"; for (int i = 2; i <= n; ++i) { string t = s; reverse(t.begin(), t.end()); for (char &c : t) { c = c == '0' ? '1' : '0'; } s = s + "1" + t; } return s[k - 1]; } };

这两段代码逻辑完全一样：每一轮基于上一轮的字符串生成下一轮。Python 里我用reversed(s)生成反向迭代器，配合生成器表达式一次性完成“反转 + 取反”；C++ 里则是先reverse再遍历改字符。

2.2 复杂度分析：为什么 n <= 20 时模拟完全能过

很多人看到 2048、4096 这类数字会下意识觉得字符串会爆炸，但实际上 n 最大 20 时 len(20) = 2^20 - 1 = 1,048,575，一百万个字符而已，内存大约 1MB，生成过程总字符操作量在 200 万级别，LeetCode 上跑起来很快。

所以模拟解法在这道题里不是“过不了只能优化的备胎”，而是一个完全合规的答案。官方题解甚至也把模拟列为主要方法之一。

模拟的时间复杂度是 O(2^n)，空间复杂度是 O(2^n)。n = 20 时没问题，但你要有这个意识：如果 n 变成 30，长度直接破十亿，模拟就立刻不可行。这正是递归解法存在的意义。

2.3 什么时候必须放弃模拟

当 n 很大，或者题目改成多组查询、每次问不同的 k 时，模拟就不合适了。因为模拟的代价和整个字符串长度绑定，而递归解法只沿着一条从 k 到根的路径走，和总长度没有关系。

还有一个隐藏问题：Python 里字符串是不可变对象，每次s = s + "1" + t都会创建一个新字符串，如果 n 很大，这个拼接开销会非常难看。虽然本题 n 小无所谓，但写代码时要明白你在付出什么代价。

3. 方案二：递归（数学）自顶向下定位

3.1 核心递推关系推导

递归的思路不是“构造整个串”，而是从目标位置 k 出发，不断判断它落在当前字符串的哪个区域，然后缩小问题规模。

设当前处理的是 Sn，长度为 L = 2^n - 1，中间位置 mid = 2^(n-1)。

分三种情况：

• 如果 k == mid，说明 k 正好落在中位，直接返回 "1"。
• 如果 k < mid，说明 k 落在左半边。左半边就是 S(n-1) 原样，所以问题变成 findKthBit(n-1, k)。
• 如果 k > mid，说明 k 落在右半边。右半边是 S(n-1) 反转取反后的结果。利用对称关系，右侧位置 k 对应左侧位置 L - k + 1，并且该位置的值要取反。所以问题变成 invert(findKthBit(n-1, L - k + 1))。

举个例子验证。求 S3 的第 6 位，n=3, k=6。L = 7，mid = 4，k > mid，所以找 S2 的第 L - k + 1 = 2 位，然后取反。S2 = "011"，第 2 位是 "1"，取反得到 "0"。回看 S3 = "0111001"，第 6 位确实是 "0"。

再看一个直接命中中位的例子。求 S3 的第 4 位，k == mid == 4，直接返回 "1"，S3 第 4 位确实是 "1"。

3.2 递归代码实现

Python 递归写法：

def findKthBit(n: int, k: int) -> str: if n == 1: return "0" length = (1 << n) - 1 # 2^n - 1 mid = 1 << (n - 1) # 2^(n-1) if k == mid: return "1" if k < mid: return findKthBit(n - 1, k) mirrored = length - k + 1 return "1" if findKthBit(n - 1, mirrored) == "0" else "0"

C++ 递归写法：

class Solution { public: char findKthBit(int n, int k) { if (n == 1) return '0'; int length = (1 << n) - 1; int mid = 1 << (n - 1); if (k == mid) return '1'; if (k < mid) return findKthBit(n - 1, k); int mirrored = length - k + 1; char val = findKthBit(n - 1, mirrored); return val == '0' ? '1' : '0'; } };

这里最容易写错的是对称位置。注意 L - k + 1 这个公式里的 L 是当前层的总长度，不是 mid。有些题解写成 mid * 2 - k，其实 mid * 2 = 2^n，和 length + 1 = 2^n 相等，所以 mid * 2 - k 与 length - k + 1 数值上完全一样。两种写法都可以，但你得知道它们为什么等价，别混着用。

取反这一步也容易漏。很多人递归到findKthBit(n-1, mirrored)就直接返回结果，忘记了右半边的字符已经被整体取反过，导致答案全错。建议在代码里单独写一行赋值，再返回取反结果，强迫自己不要漏。

3.3 递归改迭代：把函数栈变成循环

递归版本空间复杂度是 O(n)，因为递归深度最多 n 层。如果想进一步压到 O(1) 空间，可以把递归改写成迭代，核心思想是维护一个翻转向标 flip。

每次进入右半边，相当于把答案取反一次。如果进入右半边的次数是奇数，最终结果就要翻转；如果是偶数，结果不变。沿着这个思路可以写：

def findKthBit(n: int, k: int) -> str: flip = 0 while n > 1: length = (1 << n) - 1 mid = 1 << (n - 1) if k == mid: return "0" if flip & 1 else "1" if k > mid: k = length - k + 1 flip ^= 1 n -= 1 return "0" if flip & 1 else "1"

用 S3 第 6 位验证：n=3, k=6，进入右半边，k 变成 2，flip 变成 1，n 变 2；此时 mid=2，k == mid，因为 flip 是奇数，返回 "0"。结果正确。

这个迭代版本是我个人比较喜欢的写法，因为除了时间 O(n) 以外，空间占用是 O(1)，而且循环结构比递归更容易看清状态变化。递归改迭代的核心只有一个问题：哪些信息在递归返回时要用？本题中需要的信息只有“翻转次数”，所以我们用一个变量记录下来就行。

3.4 复杂度与正确性讨论

递归和迭代版本的时间复杂度都是 O(n)，每一轮只做常数次判断和一次子问题调用，n 最多 20，所以非常快。空间上递归版是 O(n) 的调用栈，迭代版是 O(1)。

时间复杂度差距最直观的体现是：模拟要处理一百万个字符，递归只需要沿着路径处理不到 20 层。这就是“构造全部”和“定位单个”的本质区别。你能从这题里带走的最重要的思维方式，就是看到“找第 k 个元素”这类问题时，先想能不能不构造完整个序列，而是直接从位置反推。

4. 两种方案对比与选型建议

4.1 复杂度与代码量对照

如果把代码量算进去，三种方案相差不大，都不到 15 行。但理解成本差很多：模拟几乎是零思考，递归需要想清楚对称映射，迭代则要在递归之上再抽象一层“翻转奇偶性”。

4.2 实际做题时该选哪个

我的建议是分场景。

如果是第一次见这道题，先写模拟。原因很简单：模拟能保证你在 3 分钟内拿到一个正确解，建立起信心，也能帮你验证自己对构造规则的理解有没有偏差。LeetCode 上 n 给到 20，模拟在时间和空间上都不会翻车。

如果是在面试或者准备长期刷题，那就必须把递归解法掌握到能默写的程度。面试官大概率会在你给出模拟后追问一句“能不能优化？”，这时候你能流畅讲出中位、对称、取反的递归过程，印象分会完全不同。如果你还能顺手写出 O(1) 空间的迭代版，那基本是加分项。

顺便说一句递归和迭代的区别，这也是很多初学者绕不过去的问题。递归是把问题分解成同结构的子问题，依赖函数调用栈保存中间状态，代码直观但可能栈溢出；迭代是手动维护状态，省去调用栈，代码往往更绕。本题里迭代版只需要维护一个 flip 布尔量，属于比较轻松的改写。

5. 从这道题延伸出去：对称取反的通用套路

5.1 位置对折与翻转次数的本质

递归解法背后藏着一个更通用的模型：从位置 k 出发，每往上一层，如果 k 在中位左侧，什么都不变；如果 k 在中位右侧，就把 k 映射到左半边的对称位置，同时记录一次“翻转”。这个行为很像把一张纸条反复对折，然后问某个折痕位置在展开后是正面还是反面。

用这个思路可以总结出一句话：答案的最终值取决于 k 一路向上被“镜像”了多少次，以及最后落在 S1 的那个位置是 0 还是 1。迭代版本里的 flip 就是在统计镜像次数，所以当 k 在某层命中中位时，可以根据 flip 奇偶直接返回。

这个“对折定位”的模型在很多自相似构造问题里都出现过，熟练之后你会形成条件反射：看到S(n) = f(S(n-1))这种结构，第一反应就是能不能从第 k 位反推回第几位，而不是从头生成。

5.2 同类题目联想

LeetCode 779 题“第K个语法符号”和这题思路高度相似，它同样是每一行由上一行经过模式扩展生成，需要从目标位置反推父层位置。还有一类“镜像二叉树”的遍历题，也是利用左右子树对称关系来递归定位。遇到这些题，核心套路都是：找中位分界、判断落在哪一侧、把当前层的 k 映射到上一层的某个位置、根据规则决定是否取反或翻转。

另外，二进制反射格雷码的构造也带有类似的对称生成特征，如果你对位运算有兴趣，可以横向对比着看。不过那属于扩展内容，本题掌握到迭代版就足够了。

6. 常见错误与排错实录

6.1 最容易翻车的四个细节

第一，k 的索引类型。k 从 1 开始，不是 0。模拟解法里必须用s[k-1]，很多人在小数据上测不出来，等到 n 大一点就越界报错了。

第二，递归时忘记取反。右半边是经过 invert 的，递归查完左半边的对称位置后，如果直接返回，结果就错了。检查方法很简单：构造一组 k 落在右侧的用例，比如 S3 的 k=6，答案应当是 "0"。

第三，对称位置算错。前面说过length - k + 1和mid * 2 - k等价，但你不能一会儿用 length 一会儿用 mid。我见过很多人写成mid - k + 1，这就不对了。建议统一用当前层长度 L 来表达，不容易混。

第四，递归函数返回值类型。题目要求返回字符 "0" 或 "1"，不是整数 0、1。Python 里如果返回数字，类型检查或字符串拼接时会出问题。

6.2 我常用的验证与调试方法

我刷这题时没有直接提交，而是先写了个模拟版当“裁判”，再写递归版，然后随机取 n 和 k 对拍。对拍逻辑很简单：模拟版一定正确，递归版结果和它不一致就说明递归映射写错了。对于这种递归题，对拍是最高效的排错手段，比自己盯着代码猜快得多。

另一个技巧是在递归函数里临时打印参数，比如打印(n, k)，观察每一轮递归的路径。正常情况应该是 n 严格递减，k 落在 1 到 2^n - 1 之间。如果你发现 k 在某层变成了 0 或者大于长度，那一定是映射公式的问题。

手算小数据也很有用。S3 = "0111001"，你可以把 k=1 到 7 全部手推一遍答案，再用递归代码验证。这个小串只有 7 位，几分钟就能做完，但能帮你确认中位判断、左递归、右递归取反三个分支都正确。

7. 写在最后：一点个人刷题体会

我自己刷这类“字符串序列 + 找第 k 位”的题目，最大的体会是不要急着追求最优解。先写一个一定能跑对的模拟版，保证自己对题意的理解不出偏差，然后再去想怎么优化，这样心态稳得多。LeetCode 很多题的数据范围其实都允许“暴力”，但面试里真正值钱的是你能不能从暴力里提炼出递归、从递归里再优化到迭代。

1545 这道题很适合收藏进你的“递归专项”清单，因为它在极短的代码里浓缩了三个常用套路：中位分界、位置映射、奇偶翻转。你把这道题的递归思路打通之后，再遇到 779 这类题会轻松很多。最后再说一个小技巧：所有类似的“对称反转取反”结构，都可以用“从目标位置反向追踪 + 统计翻转次数”的方法统一处理，这比每次重新构造字符串要通用得多。