题目名称

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

例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。
给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）

示例

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

题解

这里采用的是找规律的方法
首先
第一行 0
第二行 01
第三行 0110
第四行 0110 1001
第五行 0110 1001 1001 0110
……

通过上述例子，我们可以发现，每一行的后半段是前半段的 相反
这样我们可以采用递归的方式
通过获取 k 在第 i 行 中的映射位置，然后依次递归查找到 k = 1 的行数，这时 需要将 0 进行 递归深度 deep 次翻转
也就是说 如果deep 为偶数 不变，为奇数则翻转为 1
这里则采用 二级制数位运算符 ^(非)，只有两个都不相同才返回
也就是 0 ^ 1 或者 1 ^ 0 = 1
1 ^ 1 或者 0 ^ 0 = 0
这样就可以模拟出数字 0和1的翻转

答案

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
 var kthGrammar = function(n, k) {
  if(k === 1) return 0
  if(k > (1 << (n - 2))) {
    return 1 ^ kthGrammar(n - 1, k - (1 << (n - 2)))
  }
  return kthGrammar(n - 1, k)
};