中等

问题描述

我们构建了一个包含 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 <= 2n - 1

递归

不难发现，每一行的前半部分和上一行完全一致，后半部分是上一行的相反，那么会有以下两种情况：

• 如果 $k$ 在前半部分，那么第 $k$ 个字符就是上一行的第 $k$ 个字符，直接递归 $kthGrammar(n - 1, k)$ 即可。
• 如果 $k$ 在后半部分，那么第 $k$ 个字符就是上一行的第 $k - 2^{n - 2}$ 个字符的反转，即 $kthGrammar(n - 1, k - 2^{n - 2}) \oplus 1$。

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var kthGrammar = function (n, k) {
  if (n === 1) return 0
  const mid = 2 ** (n - 2)
  if (k <= mid) {
    return kthGrammar(n - 1, k)
  } else {
    return 1 ^ kthGrammar(n - 1, k - mid)
  }
}

• 时间复杂度：$O(\log{n})$
• 空间复杂度：$O(1)$