第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

题解

根据N和K递归判断，当前行的第K个，如果k为偶数应该看上一行的第k/2个，否则看上一行的k/2+1个，注意js应为Math.floor(k/2)+1。 然后根据上一行的指定结果判断，如果k为偶数，返回相反的数，如果为奇数，返回相同的数。

/**
 * @param {number} N
 * @param {number} K
 * @return {number}
 */

var kthGrammar = function(N, K) {
    let res;
    if(N===1)return 0;
    if(K%2){
        res = kthGrammar(N-1,Math.floor(K/2)+1);
    }else{
        res = kthGrammar(N-1,K/2);
    }
    if(K%2){
        return res;
    }else{
        return res===0?1:0;
    }

};

总结

一开始头脑空白，怎样思考找规律？

按照方法一，我们可以尝试写表中的前几行：

00

0101

01100110

0110100101101001

⋯

我们可以注意到规律：每一行的后半部分正好为前半部分的“翻转”——前半部分是 00 后半部分变为 11，前半部分是 11，后半部分变为 00。且每一行的前半部分和上一行相同。我们可以通过「数学归纳法」来进行证明。

有了这个性质，那么我们再次思考原问题：对于查询某一个行第 kk 个数字，如果 kk 在后半部分，那么原问题就可以转化为求解该行前半部分的对应位置的“翻转”数字，又因为该行前半部分与上一行相同，所以又转化为上一行对应对应的“翻转”数字。那么按照这样一直递归下去，并在第一行时返回数字 00 即可。