# 779. 第 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

提示:

  • 1 <= n <= 30
  • 1 <= k <= $2^n - 1$

# 题解

这道题和腾讯笔试题很像。
本质上每一次操作都是在上一行基础上添加其按位取反后的结果。

class Solution {
public:
int kthGrammar(int n, int k) {
k--;
int res = 0;
while (k > 0) {
k &= k - 1;
res ^= 1;
}
return res;
}
};

复杂度分析

  • 时间复杂度:$O (logk)$
  • 空间复杂度:$O (1)$