0779：第K个语法符号（1571 分）

力扣第 779 题

题目

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

分析

#1

为了方便，令 x = k - 1 使得从 0 开始。

第 n 行的第 x 位由第 n-1 行的第 x//2 位生成。如果 x 是偶数，则该字符与原字符相同，否则是原字符取反。

因此考虑递归。最简单的子问题是 n = 1 时，显然为 0。

1
2
3
4

def kthGrammar(self, n: int, k: int) -> int:
    def help(n, x): 
        return 0 if n == 1 else help(n - 1, x // 2) ^ (x % 2)
    return help(n, k - 1)

16 ms

#2

因为异或运算满足结合律。所以递归过程等价于将 x 的二进制的每一位异或。

因此根据 x 的二进制的 1 的个数即可得到结果。

解答

1
2

def kthGrammar(self, n: int, k: int) -> int:
    return bin(k-1).count('1') % 2

24 ms