0779. 第K个语法符号

0779. 第K个语法符号 #

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

题目大意 #

给定两个整数 n 和 k,按照下面的规则来生成字符串:

  • 第一行写上一个 0
  • 从第二行开始,每一行将上一行的 0 替换成 011 替换为 10
1
2
3
4
第一行:0
第二行:01
第三行:0110
第四行:01101001

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

解题思路 #

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

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

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

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

代码 #

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)
本站总访问量  次  |  您是本站第  位访问者