解决递归问题

1545. 找出第 N 个二进制字符串中的第 K 位 - 力扣（LeetCode）

题意：

$S_1$=“0”

$S_i=S_{i-1}+$ “1” $+reverse(invert(S_{i-1}))$

给定$n,k$，求$S_n$的第$k$个字符是$0$还是$1$

思路：

可以观察得到$S_n+1$的长度是一个首项为$2$，公比为$2$的等比数列

因此有$|S_n| = 2^{n}-1$

又因为$S_n$是由$S_{n-1}$，1，以及倒转的且每位翻转的$S_{n-1}$组成

所以$k< 2^{n-1} -1$ ， 要找$S_{n-1}$的第$k$个字符

$k=2^{n-1}-1$ ，答案为$1$

$k>2^{n-1}-1$ ,要找$S_{n-1}$的第$2^{n}-k$个字符，并将其翻转转

basecase:n=1时，答案为$0$

class Solution {
public:
    char findKthBit(int n, int k) {
        if(n==1){
            return '0';
        }
        if(k==(1ll<<n-1)){
            return '1';
        }
        if(k<(1ll<<n-1)){
            return findKthBit(n-1,k);
        }
        return findKthBit(n-1,(1ll<<n)-k)^1;
    }
};