第 K 个语法符号

我们构建了一个包含 n 行( 索引从 1 开始 )的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的 0 替换为 01，1 替换为 10。
例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第 3 行是 0110 。
给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）

  • 输入: n = 1, k = 1
    输出: 0
    解释: 第一行：0

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

1
2
3
4
5
6
var kthGrammar = function (n, k) {
    if (n === 1) {
        return 0;
    }
    return (k & 1) ^ 1 ^ kthGrammar(n - 1, (k + 1) / 2);
};