题目描述
思路解析
一句话答案：LeetCode 1545 找出第 N 个二进制字符串中的第 K 位：整串按对称规则递归生成，不拼串，靠中点把第 k 位一层层折回上一层——中点取 1、左半照降、右半镜像取反，O(n) 定位。
这串是怎么长出来的，第 k 位又指谁
给两个正整数 n 和 k，背后有一列二进制字符串：S1 是 "0"；往后每个 Si 都是前一个 S(i-1)，接一个 "1"，再接上「把 S(i-1) 每位取反、整串再反过来」的那段——取反就是 0 换成 1、1 换成 0。于是 S2 是 "011"，S3 是 "0111001"，S4 是 "011100110110001"。要返回 Sn 第 k 位是 "0" 还是 "1"。题面三组：n=3 找第 1 位得 "0"，n=4 找第 11 位得 "1"，n=2 找第 3 位得 "1"。
把整串拼出来再数第 k 位，为什么白算
Sn 长度是 2^n - 1，n 一到 20 就是上百万位。照规则把整串拼出来再数第 k 位，得先造一条百万长的串，时间和空间都吃到 O(2^n)。可题目只问一位，拼整串把用不上的九成九也算了个遍。
中点永远是 1，左右两半天生对称
看构造式：Si 正中间那位是拼接时单独插进去的 "1"，位置恰好是第 2^(i-1) 位，永远是 1，不必算。它把整条串劈成对称的左右两半，各长 2^(i-1) - 1。左半正是上一层的 S(i-1)、一字未改；右半是 S(i-1) 先取反、再反过来得到的。所以右半第 k 位，正是左半第 2^i - k 位取反后的值——镜像折回位置，取反改正值。第 k 位靠位置算术就能推，跟串多长无关。
只盯中点的左右，问题怎么一层层缩小
定位第 k 位只有三条岔路：k 等于中点，答案当场是 1；k 在左边，位置不变直接降到上一层；k 在右边，镜像到第 2^i - k 位折回左半、记一次取反再降。降层途中只攒取反的奇偶，走右半每折一次多取反一次。折到 S1 那唯一的 "0"，累计取反偶数次两两抵消、答案是 0，奇数次翻成 1。
n=4 找第 11 位、n=3 找第 1 位，各折几层
照题面 n=4 找第 11 位走一遍。S4 中点第 8 位，11 ＞ 8 落右半，镜像到第 2^4 - 11 = 5 位、记一次取反，降到 S3 第 5 位。中点第 4 位，5 ＞ 4 又落右半，镜像到第 2^3 - 5 = 3 位、再取反一次，降到 S2 第 3 位。中点第 2 位，3 ＞ 2 仍落右半，镜像到第 2^2 - 3 = 1 位、第三次取反，降到 S1。S1 是 "0"，一路 3 次取反是奇数，把 0 翻成 1，答案 "1"。
再看 n=3 找第 1 位，全走左半：S3 中点第 4 位、1 ＜ 4 落左半降到 S2，S2 中点第 2 位、1 ＜ 2 又落左半降到 S1，第 1 位就是 "0"，全程 0 次取反，答案 "0"，左半一路什么都不必动。
别真把百万位拼出来，右半那次取反也漏不得
每折一层层数减 1，最多从第 n 层折到第 1 层，一共 O(n) 步；递归栈最深压 n 层，空间 O(n)，改成循环能压到 O(1)。会写错的在别处：落右半忘了取反、照搬镜像后的值，凡走右半的查询全答错；k 等于中点时要立刻返回 1，当普通位置往下折会越界。边界也直白：n=1 时串只第 1 位、恒是 0，而 k 一旦撞上中点（如 n=2 第 2 位）就恒是 1。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢:中点第 2^(n-1) 位恒为 "1"。k = 中点直接是 1;k 在左半就降到 S(n-1) 同一个 k;k 在右半镜像到第 2^n - k 位、翻转一次再降层。一路折到 S1,翻转奇偶定答案。
例一 · n=3 k=5 · 看清舞台：七个格子代表 S3 的第 1 到第 7 位,现在全是问号,因为我们打算一位都不去算,只靠折叠定位。紫色指针停在第 5 位,这就是要找的目标。右边面板记三件事:当前在哪个串、要找第几位、到目前为止翻转了几次的奇偶。
例一 · 中点恒为 1：先标出正中间。S3 长度 7,正中间是第 4 位,它是构造时硬插进去的那个 "1",所以不用算就知道是 1,标成蓝色。这个中点把整串劈成对称的左右两半:左边第 1 到第 3 位,右边第 5 到第 7 位。
例一 · 第 5 位在右半段：比一比:目标第 5 位在中点第 4 位的右边,落在右半段。把左半段先压灰,我们只盯右半。右半段不是凭空来的,它是左半段 S2 先把每位取反、再整体反过来得到的,所以右半的每一位都能在左半找到对应。
例一 · 镜像到第 3 位：右半段第 k 位,正好等于第 2^n 减 k 位「取反」后的样子。这里 2 的 3 次方减 5 等于 3,也就是第 5 位的值,等于第 3 位取反。于是把目标镜像到第 3 位,并且记下一次翻转,翻转奇偶从 0 变成 1。
例一 · 问题缩小到 S2：左半段本身就是 S2,长度 3。问题干净利落地缩小成:在 S2 里找第 3 位,最后再把翻转应用回去。右边那三格已经折叠完成,压灰收起,我们的视线收回到第 1 到第 3 位。
例一 · S2 的中点也是 1：同样的套路再来一遍。S2 长度 3,正中间是第 2 位,又是插进去的那个 "1",标蓝。它把第 1 到第 3 位再次劈成左右:左边只剩第 1 位,右边只剩第 3 位。
例一 · 第 3 位又在右半：目标第 3 位在 S2 中点第 2 位的右边,又落在右半段。这一层的右半,是 S1 取反再反转得到的。把左边第 1 位先压灰,只看右边这一格。
例一 · 镜像到第 1 位：再镜像一次:2 的 2 次方减 3 等于 1,第 3 位等于第 1 位取反。把目标镜像到第 1 位,再记一次翻转,翻转奇偶从 1 翻回 0。注意奇偶现在是偶数,意味着两次取反最终会互相抵消。
例一 · 触底 S1：降到 S1 了,它就是单独一个 "0"。要找的第 1 位,值就是 0,标成绿色。这是递归的出口,再也不用往下折了。接下来只剩一件事:把途中记下的翻转应用回去。
例一 · 偶数次翻转抵消：一路上我们记了两次翻转,两次都是取反。偶数次取反相当于没动,所以底部的 0 原样保留。如果是奇数次,才需要把它翻成 1。这里是偶数,答案保持 0。
例一 · 第 5 位 = 0：把答案填回第 5 位:是 0。整个过程我们只折叠了两次、看了两个中点再落到 S1 出口,从没真的拼出 S3 那七位。注意第 3、6、7 位始终是问号,因为根本没必要去算它们。
例二 · n=3 k=2 · 命中中点：换个目标,这次找 S3 的第 2 位,看看落在左半会怎样。翻转奇偶重新从 0 起算。之前揭示过的中点蓝格还在,因为同一个 S3 它们的值不变,正好省得重标。
例二 · 第 2 位在左半段：第 2 位在中点第 4 位的左边,落在左半段。左半段最省心:它就是 S2 一字不差的原样,位置不用镜像、也不用记翻转。把右半压灰,直接降层。
例二 · 降到 S2,k 不变：问题缩小成在 S2 里找第 2 位,k 还是 2,翻转奇偶仍然是 0。左半段的好处就在这,什么都不用改,层数减一就行。
例二 · 正好踩中点：S2 长度 3,中点正是第 2 位,而我们要找的就是第 2 位,直接撞上了中点。中点恒为 "1",标成绿色,答案当场揭晓,连降层都省了。
例二 · 第 2 位 = 1：这一路全走的左半段,没碰过任何右半,翻转次数是 0,所以中点的 1 原样就是答案。S3 第 2 位是 1。可见踩中点是最快的情形,一步到位。
例三 · n=3 k=1 · 一路向左：最后一个例子,找 S3 的第 1 位,也就是整串开头。第 1 位远在中点第 4 位左边,落在左半段,降到 S2、k 仍是 1。
例三 · S2 里还在左半：到了 S2,中点是第 2 位,第 1 位还在它左边,继续落左半,降到 S1,k 依旧是 1。每一层都往左,翻转次数始终为 0。
例三 · 触底 S1：降到 S1,要找第 1 位,值是 0,标绿。一路没经过右半,0 次翻转。
例三 · 第 1 位 = 0：每个 Sn 的开头都是 S1 的那个 "0",所以任何 Sn 的第 1 位都是 0,这跟样例里 n = 3、k = 1 的答案完全吻合。三个例子走完,折叠法的左、右、命中三种走向都见过了。
总览 · 三次查询一齐回看：把三次查询的结果放一起回看:第 1 位是 0、第 2 位是 1、第 5 位是 0,都标成绿色,中点第 4 位是蓝色的 1。注意第 3、6、7 位至今还是问号,我们一次都没去算它们,这正是折叠法的精髓:要哪一位就只折哪一位,长串永远不必拼出来。
边界:n=1 只有第 1 位、恒 0;k 落中点(如 n=2 第 2 位)恒 1;n=4 第 11 位落右半,镜像到第 5 位并翻转,逐层折叠得 1。
面试重点:全程只在位置上折叠、不拼串,所以 O(n) 时间不怕百万长度;右半的取反源自 reverse(invert) 构造;参考代码用「k 是 2 的幂」一步识别中点,等价于动画里逐层走到中点。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def findKthBit(self, n: int, k: int) -> str: def dfs(n: int, k: int) -> int: if k == 1: return 0 if (k & (k - 1)) == 0: return 1 m = 1 << n if k * 2 < m - 1: return dfs(n - 1, k) return dfs(n - 1, m - k) ^ 1 return str(dfs(n, k))复杂度
- 时间：O(n)，每折叠一次,层数 n 就减 1,最多从第 n 层降到第 1 层,一共 O(n) 步,每步只做几次比较与减法,都是常数操作。注意这里的 n 是字符串的「层数」,不是串的长度。串长是 2^n - 1,可能上百万,但我们从不遍历它,只沿中点折叠,所以是 O(n) 而非 O(2^n)
- 空间：O(n)，按峰值算。递归 dfs 最深会嵌套 n 层,调用栈上同时压着 O(n) 个栈帧,这是空间的主要来源。除此之外只用了 m、mid 这几个常数变量,没有开数组、没有拼字符串。若改写成循环迭代,递归栈可降到 O(1),但本题 n 最大 20,O(n) 栈深完全无压力
易错点
面试追问把动画讲成自己的话
追问n 能到 20,Sn 上百万位,真拼整串是 O(2^n),你的解法怎么把它降到可行?
追问落在右半段时,那次「取反」到底从哪来?
追问参考代码里用 k 与 k 减 1 按位与判断 2 的幂,跟动画的中点判断是一回事吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
执行操作后字典序最小的字符串
LeetCode 1625 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题