题目描述

给你两个正整数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 <= 2n - 1

思路(dfs逆推) 同ACWING.786(第K个数)

• 根据题意我们要找的是S_n的第k位 一种方式是我们直接生成S_n另一中是通过S_n去找它的第k位是怎么来的
• 通过分析我们得出以下两点结论:
• 1.S_n的长度len = (2^n)-1
• 2.S_n的前半部分是S_{n-1}中间部分(idx:len/2+1)是1后半部分是S_{n-1}先invert再reverse`
• 因此我们可以根据上面的结论去反推S_n的第k位是几
• if(k==len/2+1) return ‘1’
• if(k<len/2)[k在前半部分] return dfs(len/2,k)
• else [k在后半部分]->因为是先invert再reverse所以我们逆推的时候需要先reverse再invert
  • char c = dfs(len/2,len-k+1) return c ==‘1’ ? ‘0’ : ‘1’;

时间复杂度(每次递归减少一半 <= O(2N))

代码

class Solution {
    public char findKthBit(int n, int k) {
        int len = (1<<n)-1;
        return dfs(len,k);
    }

    private char dfs(int n,int k){
        if(n == 1) return '0';
        if(k == n/2+1) return '1';
        if(k <= n/2) return dfs(n/2,k);
        char c = dfs(n/2,n-k+1);
        return c == '1' ? '0' : '1';
    }
}