LeetCode 779 第K个语法符号

779. 第K个语法符号

在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始）

例子:

输入: N = 1, K = 1
输出: 0

输入: N = 2, K = 1
输出: 0

输入: N = 2, K = 2
输出: 1

输入: N = 4, K = 5
输出: 1

解释:
第一行: 0
第二行: 01
第三行: 0110
第四行: 01101001

这是递归类的题目，首先对特殊情况进行分析第一行和第二行 第一行的话 直接返回0 第二行的话只有两个可能0 或者 1 不像从第三行开始，因为K有四个所以可能的情况也很多，但是归根结底，研究题上给出的从第一行到第四行的规律来看，可把除第一行以外的所有行数字从中间一切两半分为两部分，右半部分的每个数字为左半部分对应位置上数字的取反。
所以这个时候只需要判断K值大小 如果K > N / 2 那么进行递归取反即可 其他情况直接递归至 N-1 即可
还有一个问题是因为递归是从N开始 如果判断每一行有多少数字从而与K的值来进行比较？
因为每一行的数字数量规律为2的N-1次方
所以可以通过对1进行左移N-1位来得到上一行数字的数量

以下为源代码：

class Solution {
public:
    int kthGrammar(int N, int K) {
        if (N == 1) {
            return 0;
        }
        if (N == 2) {
            return K == 1? 0 : 1;
        }
        //因为每一行长度为2 的n-1次方  所以要计算上一行长度就得左移
        int len = (1 << (N-1)) / 2;

    if (K <= len) {
        return kthGrammar(N-1, K);
    } else {
        //取反  用另一种方法试试
        //位于后半段 K 的值肯定大于上一行的len值 所以是k - len
        return !kthGrammar(N-1, K-len);
    }
    }
};