最容易想到的办法是模拟，挨个拼接出来，最后返回对应层级的索引。但是这个复杂度很高。另外一种想法是根据当前查询的位置 \(k\) 去反推其起点，并记录其反转次数 \(inverse\) 。如果其是从 \(s_0\)="0" 为起点，经过偶数次翻转，其值仍为 \(0\) ，反之为 \(1\) 。其是中间添加的 \(1\) 为起点同理，只不过返回结果与起点为 \(0\) 相反。
迭代写法
class Solution:def findKthBit(self, n: int, k: int) -> str:# 翻转计数inverse=0flag=Falsefor i in range(n,1,-1):# 计算2的幂使用位运算，可以避免pow的开销length=(1<<i)-1mid=length//2+1if k==mid:flag=Truebreakif k>mid:# 使用异或更方便获取奇偶性,不需要后面对2取余判断了inverse^=k//mid# 下一层查询位置k=2*mid-k# 中间1为起点 if flag:return "0" if inverse else "1"# 0为起点 return "1" if inverse else "0"
递归写法
与上面思路一致，根据 \(k\) 的位置查找到起点，然后在归的过程（return）中进行相应的翻转。
class Solution:def findKthBit(self, n: int, k: int) -> str:# 第一层，返回当前字符"0"if n==1:return "0"# mid位置也可以用位运算计算 1<<(n-1)，为mid返回字符“1”if k==1<<(n-1):return "1"# 如果在mid之前 不需要翻转直接返回即可if k<1<<(n-1):return self.findKthBit(n-1,k)# 需要翻转，取出找到的字符，return时翻转res=self.findKthBit(n-1,(1<<n)-k)return "0" if res=="1" else "1"