0779. 第K个语法符号 #

• 标签：递归
• 难度：中等

题目大意 #

描述：给定两个整数 $n$ 和 $k$​。我们可以按照下面的规则来生成字符串：

• 第一行写上一个 $0$。
• 从第二行开始，每一行将上一行的 $0$ 替换成 $01$，$1$ 替换为 $10$。

要求：输出第 $n$ 行字符串中的第 $k$ 个字符。

说明：

• $1 \le n \le 30$。
• $1 \le k \le 2^{n - 1}$。

示例：

• 示例 1：

1
2
3
4
5

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

• 示例 2：

1
2
3
4
5
6
7

输入: n = 4, k = 4
输出: 0
解释: 
第一行：0
第二行：01
第三行：0110
第四行：01101001

解题思路 #

思路 1：递归算法 + 找规律 #

每一行都是由上一行生成的。我们可以将多行写到一起找下规律。

可以发现：第 $k$ 个数字是由上一位对应位置上的数字生成的。

• $k$ 在奇数位时，由上一行 $(k + 1) / 2$ 位置的值生成。且与上一行 $(k + 1) / 2$ 位置的值相同；
• $k$ 在偶数位时，由上一行 $k / 2$ 位置的值生成。且与上一行 $k / 2$ 位置的值相反。

接下来就是递归求解即可。

思路 1：代码 #

1
2
3
4
5
6
7
8

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 0:
            return 0
        if k % 2 == 1:
            return self.kthGrammar(n - 1, (k + 1) // 2)
        else:
            return abs(self.kthGrammar(n - 1, k // 2) - 1)

思路 1：复杂度分析 #

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。