企业官网建设流程全解析

上周在群里看到有人讨论这道题，当时第一反应是“直接生成字符串不就行了”，但真动手写下去才发现，如果只是用模拟的思路，面试官通常会马上追问一句：“如果不构造出完整字符串，能不能直接把第 K 位算出来？”那一下很能check你对递归结构有没有真正理解。

这篇文章就以 LeetCode 1545 的完整解题过程为主线，从题目规则、规律拆解、递归分治，再到迭代翻转优化，把从“怎么想到”到“为什么能这样做”的全过程梳理清楚。如果你最近在刷递归、分治、找规律类的题目，或者想通过一个经典题把“递归生成序列”这类的套路打通，这篇应该能给你一些可以落地的思路。

1. 先看清题目在说什么：S_n 的构造规则和边界

1.1 输入输出与核心约束

题目本身很短，但很多新手容易在“第 K 位”到底是 0-index 还是 1-index 上犯迷糊。LeetCode 1545 里的 K 是 1-index 的，也就是 S_n 这个字符串从左到右，第一个字符是第 1 位。这一点非常关键，后面所有代码都以这个为前提。

输入是两个参数n和k，其中n表示我们要处理的是第 n 个字符串 S_n，k表示在 S_n 中找第 k 位字符。约束是1 <= n <= 20，1 <= k <= 2^n - 1。k的约束其实暗示了一件事：S_n 的长度是固定的，一定是2^n - 1，所以k一定在合法范围内。

再看生成规则：

• S_1 = "0"
• 对于i > 1，S_i = S_{i-1} + "1" + reverse(invert(S_{i-1}))

其中invert是把每个字符翻转：0 变 1，1 变 0。reverse是把整个字符串倒序。

这个规则第一次看会觉得绕，尤其“反转”和“取反”在一起的时候。但其实只要手写几项，规律很快就能浮出来。

1.2 手写前几项，把抽象规则变成具体样例

我刷题有一个习惯：先不看题解，把前 3 到 4 项硬写出来，亲眼看一看数字长什么样。这道题特别适合手推。

• S_1 = "0"，长度 1
• S_2 = S_1 + "1" + reverse(invert(S_1)) = "0" + "1" + reverse("1") = "011"，长度 3
• S_3 = S_2 + "1" + reverse(invert(S_2)) = "011" + "1" + reverse("100") = "011" + "1" + "001" = "0111001"，长度 7
• S_4 = S_3 + "1" + reverse(invert(S_3)) = "0111001" + "1" + reverse("1000110") = "0111001" + "1" + "0110001" = "011100110110001"，长度 15

把前几项放在一起看：

肉眼能观察到的第一件事是：长度每次都变成原长度 * 2 + 1，所以 S_n 长度是2^n - 1。第二件事是：每个 S_n 的中间位置恰好是 S_{n-1} 长度再加 1，也就是2^(n-1)这个位置，且中间字符一定是"1"，S_2、S_3、S_4 都验证了这个规律。

其实这时候“递归二分”的直觉已经可以出来了：既然每个新串都是左右两段包着中间一个字符，我要找第 k 位，完全可以先判断 k 落在中间、左边、还是右边，再决定下一步往哪里走。

1.3 输入规模：直接拼接字符串是不是也能过

很多人第一直觉是：直接模拟生成 S_n，然后取第 k 位不就行了？

我承认，对于这道题的约束来说，直接模拟确实能跑过。n 最大是 20，S_20 的长度是2^20 - 1 = 1048575，只约 100 万个字符。就算每次都反转、取反、拼接，总操作量大概也就是 200 万次字符处理，Python 在 LeetCode 的时限下跑完绰绰有余。

如果写成模拟，核心代码大概是这样：

def findKthBit(n: int, k: int) -> str: s = "0" for i in range(2, n + 1): invert = ''.join('1' if c == '0' else '0' for c in s[::-1]) s = s + '1' + invert return s[k - 1]

这个代码非常直观，也完全正确。但问题在于：它把题目考查的重点完全跳过了。题目要的不是“你会用字符串拼接”，而是“你能不能在不构造完整字符串的情况下，利用递归生成规律直接定位第 k 位”。如果你只是模拟过了，面试官进一步问“如果 n 变成 50，长度是 2^50 这个量级，字符串都不可能存进内存，你还能怎么算”，这时候不会递归分治就会卡住。

所以我更推荐把这题当成一个递归和二进制规律题来做。模拟代码可以作为验证答案的辅助工具，但真正的正解是往下这一套。

2. 把构造过程拆成“中轴+左半+右半”

2.1 反转和取反的先后顺序有讲究吗

在推导递归关系之前，先解决一个很多人会绕晕的点：reverse(invert(S))和invert(reverse(S))到底是不是同一个东西？

答案是：是同一个东西。

原因很简单：对一个二进制字符串来说，反转操作只改变字符的排列顺序，不改变每个位置上的字符值；取反操作只改变每个位置上的字符值，不改变排列顺序。这两个操作互相不干扰，所以先反转再取反，和先取反再反转，得到的结果一模一样。

举个例子：S = "0111001"。

• 先取反再反转：取反得到 "1000110"，反转得到 "0110001"
• 先反转再取反：反转得到 "1001110"，取反得到 "0110001"

结果都是"0110001"。这说明我们在写代码的时候，完全可以先反转再逐位取反，也可以先取反再反转，怎么方便怎么来。

这个性质为什么重要？因为后面推导右侧对应关系时，我们只需要关心“右侧 = 左侧的反转取反”，而不需要纠结哪个操作先执行。

2.2 第 k 位落在三个区域时的对应关系

把 S_n 拆开来看，它的结构非常标准：

S_n = [左半部分] + [中间位 1] + [右半部分]

其中：

• 左半部分就是 S_{n-1}
• 中间位就是"1"，位置是mid = 2^(n-1)
• 右半部分是左半部分的反转加取反

这样一来，S_n 总长度是len = 2^n - 1。如果我们想知道第 k 位是什么，只需要分三种情况：

1. 如果k == mid，说明落在中间位，直接返回'1'。
2. 如果k < mid，说明落在左半部分。左半部分就是 S_{n-1}，所以问题直接变成“在 S_{n-1} 中找第 k 位”。
3. 如果k > mid，说明落在右半部分。右半部分是左半部分的反转取反，所以不能直接递归到 S_{n-1} 的第 k 位，而是要先找到它在左半部分对应的原始位置。

这里的关键就是第三种情况的索引映射。

2.3 右侧位置的反向映射，用实例验证

右半部分是左半部分倒过来以后再取反。所以如果某个位置在第 k 位落在右半段，我要在 S_{n-1} 中找到它对应的位置，需要把 k 从“右半段中的位置”映射回“左半段的镜像位置”。

公式是：

mirror = len - k + 1

为什么是这个公式？因为整个字符串是回文式结构，最后一位len对应左半部分的第 1 位，倒数第二位len - 1对应左半部分的第 2 位，依此类推。所以位置 k 在左侧对应的镜像位置就是len - k + 1。

找到这个镜像位置之后，还要注意一点：右侧的值是对左侧镜像位置的值取反得到的。所以递归拿到dfs(n-1, mirror)以后，还要做一次取反。

拿一个实际数字验证一下。

S_4 = "011100110110001"，长度 15，中间位置是 8。我要找第 11 位。

• len = 15，mid = 8
• k = 11 > mid，所以落在右侧
• 镜像位置：mirror = 15 - 11 + 1 = 5
• 递归求 S_3 的第 5 位：S_3 = "0111001"，第 5 位是'0'
• 右侧需要取反，所以最终结果是'1'
• 查 S_4 第 11 位，数一下：位置 1 到 15 分别是0 1 1 1 0 0 1 1 0 1 1 0 0 0 1，第 11 位确实是'1'

这个映射关系验证通过以后，递归递归公式其实就已经定下来了。

3. 递归分治：最贴合构造规则的写法

3.1 递归函数的边界条件和参数含义

递归写法的核心是定义一个函数dfs(cur_n, cur_k)，表示“在 S_cur_n 这个字符串中找到第 cur_k 位”。

边界条件是cur_n == 1。因为 S_1 就是"0"，所以直接返回'0'。

但要注意，并不是所有小于中间位置的情况都一路递归到cur_n == 1。在递归过程中，如果cur_k == mid，直接返回'1'，不需要继续往下走。这个分支本质上也是递归的终止条件之一。

3.2 三种情况的分支处理

递归函数主体按前面拆解的三段逻辑处理：

def findKthBit(n: int, k: int) -> str: def dfs(cur_n: int, cur_k: int) -> str: if cur_n == 1: return '0' mid = 1 << (cur_n - 1) length = (1 << cur_n) - 1 if cur_k == mid: return '1' if cur_k < mid: return dfs(cur_n - 1, cur_k) mirror = length - cur_k + 1 bit = dfs(cur_n - 1, mirror) return '1' if bit == '0' else '0' return dfs(n, k)

这个代码最需要注意的地方是：不要试图在右侧分支里再去套一层“递归到右半部分”。右半部分是“左半部分的反转取反”，所以我们永远只需要递归到左侧的子问题，只是在递归返回后做一次取反。

还有一个容易被忽略的细节：cur_k < mid时，我们是直接递归到dfs(cur_n - 1, cur_k)，因为左半部分就是 S_{cur_n-1} 本身，索引不变。而cur_k > mid时，需要先把索引改成mirror。

3.3 复杂度分析和为什么递归深度不用愁

这个递归每次最多让cur_n减 1，所以递归层数最多是 n 层。题目约束 n 最大是 20，完全不用担心栈溢出。

时间复杂度是 O(n)，因为每一层递归只做常数次判断、一次位置映射，然后最多向下递归一次。空间复杂度是 O(n)，来自递归栈。这个复杂度比直接模拟的 O(2^n) 有质的优势，尤其当 n 比较大的时候，比如 n 等于 50，长度是 2^50 这个量级，模拟根本没办法做，但递归解法只需要 50 层就能算出来。

3.4 用几个样例验证代码

我们用几个手算过的样例走一遍：

• dfs(1, 1)：直接返回'0'，S_1 第 1 位确实是'0'
• dfs(2, 3)：mid = 2，length = 3，k = 3 > mid，mirror = 3 - 3 + 1 = 1，dfs(1, 1)返回'0'，取反后返回'1'，S_2 = "011" 第 3 位确实是'1'
• dfs(3, 5)：mid = 4，length = 7，mirror = 7 - 5 + 1 = 3，dfs(2, 3)返回'1'，取反后返回'0'，S_3 = "0111001" 第 5 位确实是'0'

三个样例全部通过，说明递归逻辑和映射公式是一致的。

4. 迭代翻转：把递归拍平成循环

4.1 观察：经过右侧时结果会翻转一次

递归解法虽然好懂，但有的面试官会继续追问：“能不能把 O(n) 的递归栈也去掉？”这就需要用迭代来写。

回到递归的路径去看。每次递归有以下几种情况：

• k < mid：去左半部分，字符值不变
• k == mid：直接得到'1'
• k > mid：映射到左半的镜像位置，然后字符值取反

所以整个求解过程，实际上就是一路从 S_n 往 S_1 走。每当我们经过一次“右侧”，后面最终得到的原始字符就要翻转一次。如果我们把走过的右侧次数用一个布尔值flipped记下来，那么最后只需要看 S_1 的原始字符'0'被翻转了多少次。

这个思路的关键是：不需要真正递归，只需要模拟递归的路径选择，并用一个变量累积翻转次数。

4.2 用 flipped 变量记录翻转次数

模拟递归路径时，要维护两个变量：

• cur_n：当前字符串的编号，初始是 n
• cur_k：当前要找的位置，初始是 k
• length：当前字符串的长度，初始是2^n - 1
• flipped：记录是否已经翻转了奇数次

每一层循环都做一次判断：

1. mid = 1 << (cur_n - 1)
2. 如果cur_k == mid，返回'1' if not flipped else '0'
3. 如果cur_k > mid，先把cur_k更新为length - cur_k + 1，再执行flipped = not flipped
4. 更新length = mid - 1，cur_n -= 1

注意第 3 步和第 4 步的顺序不能颠倒。如果先更新length，再去算length - cur_k + 1，用的是已经缩小的左侧长度，结果就会错。

循环结束时，cur_n已经变成 1，说明已经回溯到了 S_1 的某个位置。此时 S_1 的原始字符是'0'，如果flipped为True，说明翻转了奇数次，最终答案是'1'，否则就是'0'。

4.3 循环代码与手算验证

def findKthBit(n: int, k: int) -> str: flipped = False length = (1 << n) - 1 while n > 1: mid = 1 << (n - 1) if k == mid: return '1' if not flipped else '0' if k > mid: k = length - k + 1 flipped = not flipped length = mid - 1 n -= 1 return '1' if flipped else '0'

拿 n = 4、k = 11 再完整走一遍：

最终返回'1'，和递归结果一致。

这个路径刚好经过三次右侧，所以翻转了三次，从'0'变成'1'。如果路径中右侧次数是偶数，最终结果就会保持'0'不变。

4.4 递归 vs 迭代：实际刷题怎么选

两种方法复杂度都是 O(n)，但迭代的空间复杂度是 O(1)，递归是 O(n)。在 LeetCode 上，这两种写法都能通过，而且差异在 n 最大为 20 时根本体现不出来。

如果从面试角度讲，我更推荐先写递归版本。因为递归版本跟题目定义的构造公式是一一对应的，面试官能一眼看懂你的思路。等面试官追问“能不能优化空间”的时候，再把手里的递归改成迭代版本，这样整个回答会有层次感。

如果从工程健壮性角度看，迭代版本更稳，因为不依赖递归栈深度。虽然这道题 n 最大只有 20，但在类似结构的问题中，如果 n 可能到 10^9，递归版本虽然层数也只有 log 级别，但迭代版本始终更省资源。

5. 从这题能学到什么，以及三个最容易踩的坑

5.1 边界条件和 1-indexed 的错位

这题最大的坑就是 K 从 1 开始数。很多题解和代码里用mid = 1 << (n - 1)，这里的 mid 是 1-index 的位置。如果你下意识用 0-index 的逻辑去理解，很容易在验证时把自己绕晕。

我的建议是：拿到这种题目，先在纸上画出一个具体的 S_n，然后把 mid 位置标出来，再模拟一次 k 落在左、中、右三种情况。一旦发现某个样例输出不对，先检查是不是索引边界写错了，而不是急着改递归逻辑。

5.2 字符和整数之间的来回转换

递归版本中，dfs的返回值是字符'0'或'1'。取反的时候，我见过不少人写成bit ^ 1，但 bit 是字符串，Python 里不能这样用。

正确的取反方式有两种：

# 方式一：直接用字符判断 return '1' if bit == '0' else '0'

或者把返回值设计成整数：

def dfs(cur_n: int, cur_k: int) -> int: ... return 1 - bit

我个人更建议用字符版本，因为和题目描述对应更直观。但如果你在写位运算优化版本，用整数会方便很多，比如1 - bit一句就能搞定取反。

5.3 这类题的通用思路：找对称性和自相似结构

LeetCode 1545 不是一道孤立的题，它和另一道经典递归题 LeetCode 779 “第 K 个语法符号”非常像。779 的规则是每一行的 0 变成 01，1 变成 10，本质上也是把问题规模缩小一半，然后根据 k 落在左半还是右半来决定下一步。

这类题统一的分析套路是三层：

1. 手写前几项，找到相邻两项之间的关系
2. 把当前字符串拆成左半部分、中间位置、右半部分
3. 看第 k 位落在哪个区域，把问题转化成规模更小的子问题

一旦发现 S_n 是由 S_{n-1} 加固定字符再加 S_{n-1} 的某种变形构成的，就可以立刻往“递归二分”这个方向想。这道题里的变形是“反转取反”，779 里的变形是“0 变成 01，1 变成 10”，本质都是利用对称性传递位置信息。

我自己刷完这道题之后最大的体会是：不要一上来就写代码，先把 S_1、S_2、S_3 手写出来，盯着看五分钟，很多递归结构会自己浮出来。LeetCode 1545 就是一个典型例子，它并不需要什么高深算法，只要你肯把抽象规则翻译成具体样例，剩下的就是水到渠成的递归代码。