题目链接：https://leetcode.cn/problems/find-kth-bit-in-nth-binary-string/

题目大意：给一个字符串S1=“0”S_1=“0”S1​=“0”，接下来的字符串的递推公式为Si=Si−1+"1"+reverse(invert(Si−1))S_i=S_{i-1}+"1"+reverse(invert(S_{i-1}))Si​=Si−1​+"1"+reverse(invert(Si−1​))，其中reverse()表示将其倒转，invert()表示按位取反。给出n, k，求SnS_nSn​的第k个位。

思路：开始时想着用二进制的位运算，后来感觉数字字符串转来转去太麻烦，搜了搜发现有这个库可以用，但写了之后才发现，bitset的长度要求必须是常量，而本题的字符串的长度是一直在变的。

看了一眼题解，说用递归做，茅塞顿开。首先字符串SnS_nSn​的长度是固定的，先把所有的字符串的长度算出来。由递推公式可以知道它们的长度必然都是奇数。那么我们分成前后两段来看。

长度为len，中间位为mid = len / 2。由递推公式，若在前半段，则结果就是Sn−1S_{n-1}Sn−1​的第k位；若在正中间，就是1；若在后半段，则与Sn−1S_{n-1}Sn−1​的第n-k+1位相反。

    char findBit(int n, int k) {if (n == 1)return '0';int len = lens[n];int mid = len / 2;if (k == mid+1)return '1';else if (k <= mid)return findKthBit(n-1, k);else {if (findKthBit(n-1, len+1-k) == '1')return '0';elsereturn '1';}} 

完整代码

class Solution {
public:vector lens;char findBit(int n, int k) {if (n == 1)return '0';int len = lens[n];int mid = len / 2;if (k == mid+1)return '1';else if (k <= mid)return findKthBit(n-1, k);else {if (findKthBit(n-1, len+1-k) == '1')return '0';elsereturn '1';}} char findKthBit(int n, int k) {lens.resize(n+1, 0);lens[1] = 1;for (int i = 2; i <= n; i++)lens[i] = (lens[i-1]<<1) + 1;return findBit(n, k);}
};