给你两个正整数n和k二进制字符串Sn的形成规则如下S1 0当i 1时Si Si-1 1 reverse(invert(Si-1))其中表示串联操作reverse(x)返回反转x后得到的字符串而invert(x)则会翻转 x 中的每一位0 变为 1而 1 变为 0。例如符合上述描述的序列的前 4 个字符串依次是S1 0S2 011S3 0111001S4 011100110110001请你返回Sn的第k位字符题目数据保证k一定在Sn长度范围以内。示例 1输入n 3, k 1输出0解释S3 为 0111001其第 1 位为 0 。示例 2输入n 4, k 11输出1解释S4 为 011100110110001其第 11 位为 1 。示例 3输入n 1, k 1输出0示例 4输入n 2, k 3输出1提示1 n 201 k 2^n - 1分析字符串的最大长度为 2^20-1可以先生成所有的字符串再直接输出第 n 个的第 k 位。也可以递归检查第 k 位是由哪一位生成的。如果第 k 位处在正中间则是 1如果在右半部分则它由第 n-1 个字符串的第 2^n-k 位反转得到如果在左半部分则它与第 n-1 个字符串的第 k 位一样。递归的边界条件为 n1此时字符串只有一个 1;或者第 k 位处在第 x 个字符串的正中间位置此时为 1。char findKthBit(int n, int k) { if(n1)return 0; if(kpow(2,n-1))return 1; if(kpow(2,n-1))return 1-findKthBit(n-1,pow(2,n)-k)0; return findKthBit(n-1,k); }