第 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 即可。