779. 第K个语法符号-递归法

779. 第K个语法符号-递归法

我们构建了一个包含 n 行( 索引从 1 开始 )的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。

给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）

示例 1:

输入: n = 1, k = 1
输出: 0
解释: 第一行：0

示例 2:

输入: n = 2, k = 1
输出: 0
解释:
第一行: 0
第二行: 01

示例 3:

输入: n = 2, k = 2
输出: 1
解释:
第一行: 0
第二行: 01

这题就是挺有意思的，感兴趣的，可以好好研究一下，解题代码如下：

int length(int n){
    int len=1;
    for(int i=1;i<n;i++){
        len=len*2;
    }
    return len;
}


int f(int n,int k){
    if(n==1){
        return 0;
    }
    if(n==2&&k==2){
        return 1;
    }
     if(n==2&&k==1){
        return 0;
    }
    else{
        if(k>length(n)/2){
            int a=f(n-1,(k+1)/2);
            if(a==1){
                if(k%2==0){
                    return 0;
                }
                else{
                    return 1;
                }
            }
            else{
                 if(k%2==1){
                    return 0;
                }
                else{
                    return 1;
                }

            }
        

           
        }
        else{
            return  f(n-1,k);
        }
    }
}

int kthGrammar(int n, int k){
    return f(n,k);
   


}