leetcode 1545. 找出第 N 个二进制字符串中的第 K 位 中等

给你两个正整数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 = "0"
• S2 = "011"
• S3 = "0111001"
• S4 = "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 <= 20
• 1 <= k <= 2^n - 1

分析：字符串的最大长度为 2^20-1，可以先生成所有的字符串，再直接输出第 n 个的第 k 位。

也可以递归检查第 k 位是由哪一位生成的。如果第 k 位处在正中间，则是 '1'；如果在右半部分，则它由第 n-1 个字符串的第 2^n-k 位反转得到；如果在左半部分，则它与第 n-1 个字符串的第 k 位一样。递归的边界条件为 n==1，此时字符串只有一个 '1';或者第 k 位处在第 x 个字符串的正中间位置，此时为 '1'。

char findKthBit(int n, int k) { if(n==1)return '0'; if(k==pow(2,n-1))return '1'; if(k>pow(2,n-1))return '1'-findKthBit(n-1,pow(2,n)-k)+'0'; return findKthBit(n-1,k); }