leetcode 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

提示:

1 <= n <= 30 1 <= k <= 2n - 1

class Solution {
public:
    int zero[2]={0,1};
    int one[2]={1,0};
    
    int cal(int n,int k){//查询上一层对应的数字是多少
        if(n==2){
            if(k==0){
                return 0;
            }
            else{
                return 1;
            }
        }
        int left=k%2;
        //cout<<"now n="<<n<<" and k="<<k<<endl;
        return cal(n-1,k/2)==0 ? left : 1-left;
    }
    int kthGrammar(int n, int k) {
        if(n==1)
            return 0;
        return cal(n,k-1);
    }
};

问号运算符的使用参考这里：

函数cal递归调用，查第n行下标为k的数是几。但是写的时候不知道为什么把1单独拿出来了，实际上可以合并一下:

class Solution {
public:
    int zero[2]={0,1};
    int one[2]={1,0};
    
    int cal(int n,int k){//查询上一层对应的数字是多少
        if(n==1){
            return 0;
        }
        int left=k%2;
        //cout<<"now n="<<n<<" and k="<<k<<endl;
        return cal(n-1,k/2)==0 ? left : 1-left;
    }
    int kthGrammar(int n, int k) {
        //if(n==1)
            //return 0;
        return cal(n,k-1);
    }
};