题目描述
思路解析动画文字版
记牢:中点第 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题