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 2Si S(i-1) 1 reverse(invert(S(i-1)))其中 invert 表示按位取反也就是 0 变成 11 变成 0reverse 表示把字符串整体倒序。手动推一遍就清楚了。S1 是 0所以 S2 0 1 reverse(invert(0)) 0 1 reverse(1) 011。继续推 S3S2 011invert 后是 100reverse 后还是 001所以 S3 011 1 001 0111001。S4 同理S3 0111001invert 后是 1000110reverse 后是 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 位n3, k6。L 7mid 4k mid所以找 S2 的第 L - k 1 2 位然后取反。S2 011第 2 位是 1取反得到 0。回看 S3 0111001第 6 位确实是 0。再看一个直接命中中位的例子。求 S3 的第 4 位k mid 4直接返回 1S3 第 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 0C 递归写法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 位验证n3, k6进入右半边k 变成 2flip 变成 1n 变 2此时 mid2k mid因为 flip 是奇数返回 0。结果正确。这个迭代版本是我个人比较喜欢的写法因为除了时间 O(n) 以外空间占用是 O(1)而且循环结构比递归更容易看清状态变化。递归改迭代的核心只有一个问题哪些信息在递归返回时要用本题中需要的信息只有“翻转次数”所以我们用一个变量记录下来就行。3.4 复杂度与正确性讨论递归和迭代版本的时间复杂度都是 O(n)每一轮只做常数次判断和一次子问题调用n 最多 20所以非常快。空间上递归版是 O(n) 的调用栈迭代版是 O(1)。时间复杂度差距最直观的体现是模拟要处理一百万个字符递归只需要沿着路径处理不到 20 层。这就是“构造全部”和“定位单个”的本质区别。你能从这题里带走的最重要的思维方式就是看到“找第 k 个元素”这类问题时先想能不能不构造完整个序列而是直接从位置反推。4. 两种方案对比与选型建议4.1 复杂度与代码量对照维度模拟构造递归数学迭代数学时间复杂度O(2^n)O(n)O(n)空间复杂度O(2^n)O(n)O(1)代码量很短短短理解门槛低中中偏高适用范围仅限 n 较小n 很大也可n 很大也可如果把代码量算进去三种方案相差不大都不到 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 的 k6答案应当是 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你可以把 k1 到 7 全部手推一遍答案再用递归代码验证。这个小串只有 7 位几分钟就能做完但能帮你确认中位判断、左递归、右递归取反三个分支都正确。7. 写在最后一点个人刷题体会我自己刷这类“字符串序列 找第 k 位”的题目最大的体会是不要急着追求最优解。先写一个一定能跑对的模拟版保证自己对题意的理解不出偏差然后再去想怎么优化这样心态稳得多。LeetCode 很多题的数据范围其实都允许“暴力”但面试里真正值钱的是你能不能从暴力里提炼出递归、从递归里再优化到迭代。1545 这道题很适合收藏进你的“递归专项”清单因为它在极短的代码里浓缩了三个常用套路中位分界、位置映射、奇偶翻转。你把这道题的递归思路打通之后再遇到 779 这类题会轻松很多。最后再说一个小技巧所有类似的“对称反转取反”结构都可以用“从目标位置反向追踪 统计翻转次数”的方法统一处理这比每次重新构造字符串要通用得多。