LeetCode 1545 大概是“递归构造类”题目里最值得手推一遍的代表作了。题目本身不复杂二进制字符串 S1 等于0从 S2 开始每个字符串都由三块拼成——上一轮的字符串、一个固定的1、以及上一轮字符串取反之后反转的结果。最后需要你直接回答 S_n 的第 K 位是0还是1。乍一看像是模拟题但真正考的是能不能看穿“套娃规则”在不构造完整字符串的情况下直接定位第 K 位。这篇文章会把两条路都走一遍先讲最容易理解的暴力构造再讲高效的递归二分最后给出迭代版本和常见坑点所有代码都能直接运行适合正在刷递归、分治专题的朋友也适合第一次遇到这类“套娃字符串”的读者。1. 题目拆解这个二进制字符串到底怎么长出来的1.1 规则逐字解析题目给的定义是S1 0 Si Si-1 1 reverse(invert(Si-1))先别急着背公式拆开看每个操作是什么意思。invert(x)是把字符串中的每一位翻转0变11变0。reverse(x)是把整个字符串倒过来。最后用把三段拼起来。以 S2 为例。S1 是0那么invert(0)得到1reverse(1)还是1所以 S2 0 1 1011。这里有个小细节值得注意invert和reverse两个操作是可交换的先取反再反转和先反转再取反结果完全一样。因为取反只影响每个字符本身反转只影响字符顺序两者互不干扰。代码里固定成先invert再reverse只是为了让实现顺序和题目描述一致。继续推 S3。S2 是011invert(011)得到100reverse(100)变成001于是 S3 011 1 0010111001。把 S1 到 S4 都列出来能很清楚地看到字符串变长的节奏nS_n长度101201133011100174011100110110001151.2 肉眼可见的三个规律把 S1 到 S4 摆在一起看有几个规律非常明显这些规律就是后面所有解法的核心依据。第一长度公式len(S_n) 2^n - 1。这个可以用数学归纳法证明S1 长度是 1符合假设len(S_{n-1}) 2^(n-1) - 1那么 S_n 由左半S_{n-1}、中间一个1、右半len(S_{n-1})组成总长度就是2 * (2^(n-1) - 1) 1 2^n - 1。题目里 n 最大到 20所以最长字符串长度是2^20 - 1 1048575刚好一百万个字符出头。第二中间位永远是1。因为构造规则里中间那个1是人为固定的不参与任何取反或反转操作。S_n 的总长度是奇数中位索引1-indexed正好是2^(n-1)。第三右半部分是左半部分的“镜像取反”。右半是reverse(invert(S_{n-1}))而左半就是S_{n-1}。这意味着如果知道左半某一位的值右半对称位置的字符一定是它取反后的结果。这个对称性非常关键递归解法本质上就是利用这条性质不断把问题“折叠”回左边。2. 解法一顺着规则模拟把字符串真的拼出来2.1 为什么暴力法在这个题里不丢人我看到不少题解一上来就讲递归优化但说实话这道题给定n 20的约束暴力构造字符串完全可行而且这是最不容易写错的做法。最长字符串不过约 104 万字符内存占用大约 1 MB 出头Python 里做字符串拼接也就是毫秒级完成。有人会担心字符串拼接不是有复制开销吗确实有每一轮都要把上一轮字符串复制一遍用于取反和拼接。但总字符操作量可以算一下第 i 轮新字符串长度为2^i - 1从 i2 到 n 累加总量大概是2^n级别也就是二十轮下来约两百万次字符操作。这个量级在现代机器上完全无压力。那什么时候暴力不行如果 n 提高到 30长度会到2^30 - 1超过 10 亿字符内存直接爆炸。所以暴力法适合“小数据验证思路”而递归二分才是真正的通用解法。2.2 完整代码实现Python 版class Solution: def findKthBit(self, n: int, k: int) - str: s 0 for i in range(2, n 1): prev s # 先取反 inverted .join(1 if ch 0 else 0 for ch in prev) # 再反转拼接 s prev 1 inverted[::-1] 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 prev s; string right prev; for (char c : right) { c (c 0) ? 1 : 0; } reverse(right.begin(), right.end()); s prev 1 right; } return s[k - 1]; } };两个版本思路完全一样。Python 里用生成器表达式构造反转后的右半部分比写循环再reverse()更简洁C 里reverse是标准库函数注意包含algorithm头文件不过 LeetCode 环境通常已经包含了。2.3 暴力的局限在哪里暴力的代码虽然简单但它的时间复杂度是O(2^n)空间也是O(2^n)。在本题范围内没问题但它暴露了一个本质问题为了找一位字符把整个长度为指数级的字符串全部造出来了做了大量无用功。打个比方你要查一本厚字典第 500 页的某个字暴力的做法是把整本字典重新印刷一遍再看那一页。而递归解法的思路是先判断第 500 页在整本书的前半部分还是后半部分然后一页一页排除最后只看需要的那个字所在的区域。后者显然聪明得多。3. 解法二递归二分不构造字符串也能找到第 K 位3.1 核心观察三种情况分类讨论递归解法的出发点不是“构造字符串”而是“利用 S_n 的三段式结构直接判断第 K 位落在哪里”。S_n 的结构可以画成这样左半 S_{n-1}长度 2^(n-1) - 1 中位 1第 2^(n-1) 位 右半 reverse(invert(S_{n-1}))长度 2^(n-1) - 1记mid 2^(n-1)也就是中位在 S_n 中的索引1-indexed。给定 k分三种情况如果k mid答案就是1不需要继续递归。如果k mid说明目标在左半而左半就是 S_{n-1}所以问题等价于在 S_{n-1} 中找第 k 位。如果k mid说明目标在右半。右半是左半取反后反转的结果需要把 k 映射回 S_{n-1} 的某个位置并且把结果取反。重点解释k mid时的映射公式pos 2 * mid - k。假设右半部分的第 i 位0-indexed对应左半的某个位置。右半第 i 位是invert(S_{n-1})反转后的第 i 位也就是S_{n-1}倒数第i 1位取反。k 在右半的偏移量是k - (mid 1)记作 iS_{n-1} 的长度是mid - 1所以对应到 S_{n-1} 的 1-indexed 位置为pos (mid - 1) - i (mid - 1) - (k - mid - 1) 2 * mid - k这就是pos 2 * mid - k的完整推导。理解了这个公式递归代码就只是翻译思路而已。3.2 递归代码与逐行解读class Solution: def findKthBit(self, n: int, k: int) - str: def dfs(n: int, k: int) - str: if n 1: return 0 mid 1 (n - 1) # 2^(n-1)即中位索引 if k mid: return 1 if k mid: return dfs(n - 1, k) # k mid折叠回左半结果取反 pos 2 * mid - k res dfs(n - 1, pos) return 0 if res 1 else 1 return dfs(n, k)几个细节需要说明。1 (n - 1)就是2^(n-1)位运算比2 ** (n - 1)更贴合算法题习惯也更快。递归终止条件是n 1因为 S1 固定只有一位0不用再往下分。取反操作只出现在k mid分支k mid时左半就是原来的 S_{n-1}不需要任何变换。这是初学者最容易写错的地方直接把dfs(n - 1, k)返回就完事千万别画蛇添足加取反。3.3 手动走查n4, k6纸上跑一遍递归能更直观地理解整个过程。先写出 S4 011100110110001第 6 位是0这是参考答案。调用dfs(4, 6)mid 1 3 86 8进入左半递归dfs(3, 6)。dfs(3, 6)中mid 1 2 46 4需要折叠。pos 2 * 4 - 6 2递归dfs(2, 2)并等待取反。dfs(2, 2)中mid 1 1 2k mid直接返回1。回到dfs(3, 6)拿到了1取反得到0返回0。回到dfs(4, 6)左半分支不需要取反直接得到0。对照 S4 第 6 位确实是0。整个递归过程只访问了三个节点每次都把问题规模缩小一层所以时间复杂度是O(n)空间复杂度是递归栈深度O(n)。n 最大 20 时这个优势还不明显但如果 n 扩大到 100暴力和递归的差距就是“完全跑不动”和“瞬间出结果”的区别。4. 解法三把递归改成迭代顺手省掉栈空间4.1 用循环消除递归栈的思路递归写法清晰但有些场景下你不想用递归或者面试官希望你给出迭代版本。思路其实不难递归里的“状态”只有(n, k)两个变量再加一个“当前结果是否已经被取反过”的标志。每递归一层n 就减 1如果发生了折叠k 就变成2 * mid - k同时取反标志翻转一次。这里的关键不变量是在整个循环过程中原始的答案 “当前 S_n 的第 k 位” 再按取反标志统一取反。初始时没有取反过所以标志为 False每次进入右半部分时等价于把问题映射到左半但最终答案要额外取反一次所以翻转标志如果某一步直接落在中位k mid那么当前层的答案就是1再根据标志决定是否取反。循环什么时候结束当 n 减到 1 时S1 只有一位0答案就是0按标志取反。另外也可以在循环中遇到k mid时提前返回不用等到 n 减到 1。4.2 迭代代码实现class Solution: def findKthBit(self, n: int, k: int) - str: inverted False while n 1: mid 1 (n - 1) if k mid: return 1 if not inverted else 0 if k mid: k 2 * mid - k inverted not inverted n - 1 # n 1 时S1 0 return 0 if not inverted else 1这段代码和递归版在行为上完全等价但空间复杂度从O(n)降到了O(1)。还有一个细节k mid时执行k 2 * mid - k后新的 k 一定小于mid因为 k 最大是2^n - 12 * mid - k最小是2 * mid - (2^n - 1) 2^n - 2^n 1 1最大是2 * mid - (mid 1) mid - 1。所以后续比较只需要看是否等于新一层的中位不会再无意义地大于。4.3 递归和迭代怎么选从可读性来说递归版更贴近思路本身三种情况一目了然。从实际运行来说两者时间都是O(n)n20 时差异可以忽略不计。但如果想在其他场景复用这个模式或者担心递归栈溢出迭代版更稳。对比维度递归版迭代版可读性高直接对应三分类中需要理解不变量空间复杂度O(n) 递归栈O(1)提前返回不方便可以在 kmid 时直接返回适合场景讲思路、面试推导生产代码、大 n 场景我做题时通常先写递归版理清思路验证正确后再改成迭代版这样既能保证逻辑正确又能拿到更好的空间复杂度。5. 常见问题与 Debug 实录5.1 1-indexed 的坑题目里明确说 k 从 1 开始编号但数组和字符串索引都是 0-based。暴力法最后一定要写s[k - 1]漏掉-1是最常见的错误。更坑的是某些测试用例会让你“碰巧对了”。比如 n3, k2 时S3 0111001第 2 位是1而s[2]也是1但如果 k1s[0]是0取s[1]就变成1了。所以自查时一定要覆盖 k1 这个边界别被“碰巧对”的用例骗过去。5.2 mid 到底是 2^(n-1) 还是 2^(n-1)-1这是一个特别容易混淆的点。2^(n-1) - 1是 S_{n-1} 的长度也是左半部分的长度但 S_n 的中位索引是2^(n-1)因为左半占掉前面的2^(n-1)-1位后中间那位恰好是第2^(n-1)位。记忆技巧mid 左半长度 1。写成代码就是mid 1 (n - 1)。如果这里搞错递归会立刻错乱而且很难查出来因为边界情况不会总是触发。5.3 取反位置写错递归版里只有k mid进入右半时才需要取反k mid时直接递归。常见的错误是把取反操作放在k mid分支或者忘记取反直接返回dfs(n - 1, pos)。我自己 debug 时的一个习惯是先用暴力法跑一遍小数据把 S1 到 S4 全部打印出来再用递归版逐一比对。比如检查findKthBit(4, 13)S4 第 13 位是0如果递归返回1基本就是取反逻辑写反了。5.4 相似题目LeetCode 779 第K个语法符号如果你之前刷过 LeetCode 779会发现 1545 和它有很强的血缘关系。779 的规则是第一行0之后每一行把上一行的0替换成011替换成10。两题都是“找递归构造字符串的第 K 位”但思路有明显差异。对比维度1545 第K位779 第K个语法符号构造规则S_i S_{i-1} 1 rev(inv(S_{i-1}))0→01, 1→10中位字符恒为 1无固定中位常规解法三分类递归右半折叠取反看 k 的二进制位或 popcount取反操作有折叠后需要无按规则替换即可特别提醒不要以为做过 779 就能直接套 1545。779 的经典结论是“第 n 行第 k 个字符与k-1的二进制中 1 的个数有关”但 1545 多了反转这一步导致每一层的对称轴会变化结论不能直接平移。把两题放在一起对照着看才能真正理解这两类递归构造题的底层差异。5.5 延伸思考能不能用位运算一眼看出答案递归折叠的过程本质上是把 k 在 S_n 的“对称轴”上反复折叠每折叠一次就累积一次取反。这个折叠次数和 k 的二进制表示有很强的关联。理论上可以写出基于二进制位扫描的O(n)甚至更直接的写法但推导过程比递归要绕不少所以我更推荐先把递归和迭代版本吃透。等你对折叠过程有了肌肉记忆再去看位运算写法会顺畅很多——这个可以作为刷完题目后的进阶思考题强烈建议自己推一遍比直接背结论有价值得多。个人经验谈这道题给我的最大收获不是“会做一道题”而是养成了一个判断习惯看到“递归定义 单点查询”的组合先别急着把整个结构构造出来想想能不能根据定义直接定位目标点。1545 的构造规则天然是三段式的中间位固定左右对称取反所以二分的思路几乎是一眼就能看出来的。实际写代码时我一般先用暴力解法验证小数据再用递归版理清逻辑最后才考虑要不要改写成迭代版。如果你也在刷这种题建议把 1545 和 779 放在同一天做两题对照着体会会对“递归构造、单点查询”这一类问题建立起很稳定的解题框架。
LeetCode 1545 大概是“递归构造类”题目里最值得手推一遍的代表作了。题目本身不复杂二进制字符串 S1 等于0从 S2 开始每个字符串都由三块拼成——上一轮的字符串、一个固定的1、以及上一轮字符串取反之后反转的结果。最后需要你直接回答 S_n 的第 K 位是0还是1。乍一看像是模拟题但真正考的是能不能看穿“套娃规则”在不构造完整字符串的情况下直接定位第 K 位。这篇文章会把两条路都走一遍先讲最容易理解的暴力构造再讲高效的递归二分最后给出迭代版本和常见坑点所有代码都能直接运行适合正在刷递归、分治专题的朋友也适合第一次遇到这类“套娃字符串”的读者。1. 题目拆解这个二进制字符串到底怎么长出来的1.1 规则逐字解析题目给的定义是S1 0 Si Si-1 1 reverse(invert(Si-1))先别急着背公式拆开看每个操作是什么意思。invert(x)是把字符串中的每一位翻转0变11变0。reverse(x)是把整个字符串倒过来。最后用把三段拼起来。以 S2 为例。S1 是0那么invert(0)得到1reverse(1)还是1所以 S2 0 1 1011。这里有个小细节值得注意invert和reverse两个操作是可交换的先取反再反转和先反转再取反结果完全一样。因为取反只影响每个字符本身反转只影响字符顺序两者互不干扰。代码里固定成先invert再reverse只是为了让实现顺序和题目描述一致。继续推 S3。S2 是011invert(011)得到100reverse(100)变成001于是 S3 011 1 0010111001。把 S1 到 S4 都列出来能很清楚地看到字符串变长的节奏nS_n长度101201133011100174011100110110001151.2 肉眼可见的三个规律把 S1 到 S4 摆在一起看有几个规律非常明显这些规律就是后面所有解法的核心依据。第一长度公式len(S_n) 2^n - 1。这个可以用数学归纳法证明S1 长度是 1符合假设len(S_{n-1}) 2^(n-1) - 1那么 S_n 由左半S_{n-1}、中间一个1、右半len(S_{n-1})组成总长度就是2 * (2^(n-1) - 1) 1 2^n - 1。题目里 n 最大到 20所以最长字符串长度是2^20 - 1 1048575刚好一百万个字符出头。第二中间位永远是1。因为构造规则里中间那个1是人为固定的不参与任何取反或反转操作。S_n 的总长度是奇数中位索引1-indexed正好是2^(n-1)。第三右半部分是左半部分的“镜像取反”。右半是reverse(invert(S_{n-1}))而左半就是S_{n-1}。这意味着如果知道左半某一位的值右半对称位置的字符一定是它取反后的结果。这个对称性非常关键递归解法本质上就是利用这条性质不断把问题“折叠”回左边。2. 解法一顺着规则模拟把字符串真的拼出来2.1 为什么暴力法在这个题里不丢人我看到不少题解一上来就讲递归优化但说实话这道题给定n 20的约束暴力构造字符串完全可行而且这是最不容易写错的做法。最长字符串不过约 104 万字符内存占用大约 1 MB 出头Python 里做字符串拼接也就是毫秒级完成。有人会担心字符串拼接不是有复制开销吗确实有每一轮都要把上一轮字符串复制一遍用于取反和拼接。但总字符操作量可以算一下第 i 轮新字符串长度为2^i - 1从 i2 到 n 累加总量大概是2^n级别也就是二十轮下来约两百万次字符操作。这个量级在现代机器上完全无压力。那什么时候暴力不行如果 n 提高到 30长度会到2^30 - 1超过 10 亿字符内存直接爆炸。所以暴力法适合“小数据验证思路”而递归二分才是真正的通用解法。2.2 完整代码实现Python 版class Solution: def findKthBit(self, n: int, k: int) - str: s 0 for i in range(2, n 1): prev s # 先取反 inverted .join(1 if ch 0 else 0 for ch in prev) # 再反转拼接 s prev 1 inverted[::-1] 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 prev s; string right prev; for (char c : right) { c (c 0) ? 1 : 0; } reverse(right.begin(), right.end()); s prev 1 right; } return s[k - 1]; } };两个版本思路完全一样。Python 里用生成器表达式构造反转后的右半部分比写循环再reverse()更简洁C 里reverse是标准库函数注意包含algorithm头文件不过 LeetCode 环境通常已经包含了。2.3 暴力的局限在哪里暴力的代码虽然简单但它的时间复杂度是O(2^n)空间也是O(2^n)。在本题范围内没问题但它暴露了一个本质问题为了找一位字符把整个长度为指数级的字符串全部造出来了做了大量无用功。打个比方你要查一本厚字典第 500 页的某个字暴力的做法是把整本字典重新印刷一遍再看那一页。而递归解法的思路是先判断第 500 页在整本书的前半部分还是后半部分然后一页一页排除最后只看需要的那个字所在的区域。后者显然聪明得多。3. 解法二递归二分不构造字符串也能找到第 K 位3.1 核心观察三种情况分类讨论递归解法的出发点不是“构造字符串”而是“利用 S_n 的三段式结构直接判断第 K 位落在哪里”。S_n 的结构可以画成这样左半 S_{n-1}长度 2^(n-1) - 1 中位 1第 2^(n-1) 位 右半 reverse(invert(S_{n-1}))长度 2^(n-1) - 1记mid 2^(n-1)也就是中位在 S_n 中的索引1-indexed。给定 k分三种情况如果k mid答案就是1不需要继续递归。如果k mid说明目标在左半而左半就是 S_{n-1}所以问题等价于在 S_{n-1} 中找第 k 位。如果k mid说明目标在右半。右半是左半取反后反转的结果需要把 k 映射回 S_{n-1} 的某个位置并且把结果取反。重点解释k mid时的映射公式pos 2 * mid - k。假设右半部分的第 i 位0-indexed对应左半的某个位置。右半第 i 位是invert(S_{n-1})反转后的第 i 位也就是S_{n-1}倒数第i 1位取反。k 在右半的偏移量是k - (mid 1)记作 iS_{n-1} 的长度是mid - 1所以对应到 S_{n-1} 的 1-indexed 位置为pos (mid - 1) - i (mid - 1) - (k - mid - 1) 2 * mid - k这就是pos 2 * mid - k的完整推导。理解了这个公式递归代码就只是翻译思路而已。3.2 递归代码与逐行解读class Solution: def findKthBit(self, n: int, k: int) - str: def dfs(n: int, k: int) - str: if n 1: return 0 mid 1 (n - 1) # 2^(n-1)即中位索引 if k mid: return 1 if k mid: return dfs(n - 1, k) # k mid折叠回左半结果取反 pos 2 * mid - k res dfs(n - 1, pos) return 0 if res 1 else 1 return dfs(n, k)几个细节需要说明。1 (n - 1)就是2^(n-1)位运算比2 ** (n - 1)更贴合算法题习惯也更快。递归终止条件是n 1因为 S1 固定只有一位0不用再往下分。取反操作只出现在k mid分支k mid时左半就是原来的 S_{n-1}不需要任何变换。这是初学者最容易写错的地方直接把dfs(n - 1, k)返回就完事千万别画蛇添足加取反。3.3 手动走查n4, k6纸上跑一遍递归能更直观地理解整个过程。先写出 S4 011100110110001第 6 位是0这是参考答案。调用dfs(4, 6)mid 1 3 86 8进入左半递归dfs(3, 6)。dfs(3, 6)中mid 1 2 46 4需要折叠。pos 2 * 4 - 6 2递归dfs(2, 2)并等待取反。dfs(2, 2)中mid 1 1 2k mid直接返回1。回到dfs(3, 6)拿到了1取反得到0返回0。回到dfs(4, 6)左半分支不需要取反直接得到0。对照 S4 第 6 位确实是0。整个递归过程只访问了三个节点每次都把问题规模缩小一层所以时间复杂度是O(n)空间复杂度是递归栈深度O(n)。n 最大 20 时这个优势还不明显但如果 n 扩大到 100暴力和递归的差距就是“完全跑不动”和“瞬间出结果”的区别。4. 解法三把递归改成迭代顺手省掉栈空间4.1 用循环消除递归栈的思路递归写法清晰但有些场景下你不想用递归或者面试官希望你给出迭代版本。思路其实不难递归里的“状态”只有(n, k)两个变量再加一个“当前结果是否已经被取反过”的标志。每递归一层n 就减 1如果发生了折叠k 就变成2 * mid - k同时取反标志翻转一次。这里的关键不变量是在整个循环过程中原始的答案 “当前 S_n 的第 k 位” 再按取反标志统一取反。初始时没有取反过所以标志为 False每次进入右半部分时等价于把问题映射到左半但最终答案要额外取反一次所以翻转标志如果某一步直接落在中位k mid那么当前层的答案就是1再根据标志决定是否取反。循环什么时候结束当 n 减到 1 时S1 只有一位0答案就是0按标志取反。另外也可以在循环中遇到k mid时提前返回不用等到 n 减到 1。4.2 迭代代码实现class Solution: def findKthBit(self, n: int, k: int) - str: inverted False while n 1: mid 1 (n - 1) if k mid: return 1 if not inverted else 0 if k mid: k 2 * mid - k inverted not inverted n - 1 # n 1 时S1 0 return 0 if not inverted else 1这段代码和递归版在行为上完全等价但空间复杂度从O(n)降到了O(1)。还有一个细节k mid时执行k 2 * mid - k后新的 k 一定小于mid因为 k 最大是2^n - 12 * mid - k最小是2 * mid - (2^n - 1) 2^n - 2^n 1 1最大是2 * mid - (mid 1) mid - 1。所以后续比较只需要看是否等于新一层的中位不会再无意义地大于。4.3 递归和迭代怎么选从可读性来说递归版更贴近思路本身三种情况一目了然。从实际运行来说两者时间都是O(n)n20 时差异可以忽略不计。但如果想在其他场景复用这个模式或者担心递归栈溢出迭代版更稳。对比维度递归版迭代版可读性高直接对应三分类中需要理解不变量空间复杂度O(n) 递归栈O(1)提前返回不方便可以在 kmid 时直接返回适合场景讲思路、面试推导生产代码、大 n 场景我做题时通常先写递归版理清思路验证正确后再改成迭代版这样既能保证逻辑正确又能拿到更好的空间复杂度。5. 常见问题与 Debug 实录5.1 1-indexed 的坑题目里明确说 k 从 1 开始编号但数组和字符串索引都是 0-based。暴力法最后一定要写s[k - 1]漏掉-1是最常见的错误。更坑的是某些测试用例会让你“碰巧对了”。比如 n3, k2 时S3 0111001第 2 位是1而s[2]也是1但如果 k1s[0]是0取s[1]就变成1了。所以自查时一定要覆盖 k1 这个边界别被“碰巧对”的用例骗过去。5.2 mid 到底是 2^(n-1) 还是 2^(n-1)-1这是一个特别容易混淆的点。2^(n-1) - 1是 S_{n-1} 的长度也是左半部分的长度但 S_n 的中位索引是2^(n-1)因为左半占掉前面的2^(n-1)-1位后中间那位恰好是第2^(n-1)位。记忆技巧mid 左半长度 1。写成代码就是mid 1 (n - 1)。如果这里搞错递归会立刻错乱而且很难查出来因为边界情况不会总是触发。5.3 取反位置写错递归版里只有k mid进入右半时才需要取反k mid时直接递归。常见的错误是把取反操作放在k mid分支或者忘记取反直接返回dfs(n - 1, pos)。我自己 debug 时的一个习惯是先用暴力法跑一遍小数据把 S1 到 S4 全部打印出来再用递归版逐一比对。比如检查findKthBit(4, 13)S4 第 13 位是0如果递归返回1基本就是取反逻辑写反了。5.4 相似题目LeetCode 779 第K个语法符号如果你之前刷过 LeetCode 779会发现 1545 和它有很强的血缘关系。779 的规则是第一行0之后每一行把上一行的0替换成011替换成10。两题都是“找递归构造字符串的第 K 位”但思路有明显差异。对比维度1545 第K位779 第K个语法符号构造规则S_i S_{i-1} 1 rev(inv(S_{i-1}))0→01, 1→10中位字符恒为 1无固定中位常规解法三分类递归右半折叠取反看 k 的二进制位或 popcount取反操作有折叠后需要无按规则替换即可特别提醒不要以为做过 779 就能直接套 1545。779 的经典结论是“第 n 行第 k 个字符与k-1的二进制中 1 的个数有关”但 1545 多了反转这一步导致每一层的对称轴会变化结论不能直接平移。把两题放在一起对照着看才能真正理解这两类递归构造题的底层差异。5.5 延伸思考能不能用位运算一眼看出答案递归折叠的过程本质上是把 k 在 S_n 的“对称轴”上反复折叠每折叠一次就累积一次取反。这个折叠次数和 k 的二进制表示有很强的关联。理论上可以写出基于二进制位扫描的O(n)甚至更直接的写法但推导过程比递归要绕不少所以我更推荐先把递归和迭代版本吃透。等你对折叠过程有了肌肉记忆再去看位运算写法会顺畅很多——这个可以作为刷完题目后的进阶思考题强烈建议自己推一遍比直接背结论有价值得多。个人经验谈这道题给我的最大收获不是“会做一道题”而是养成了一个判断习惯看到“递归定义 单点查询”的组合先别急着把整个结构构造出来想想能不能根据定义直接定位目标点。1545 的构造规则天然是三段式的中间位固定左右对称取反所以二分的思路几乎是一眼就能看出来的。实际写代码时我一般先用暴力解法验证小数据再用递归版理清逻辑最后才考虑要不要改写成迭代版。如果你也在刷这种题建议把 1545 和 779 放在同一天做两题对照着体会会对“递归构造、单点查询”这一类问题建立起很稳定的解题框架。
