算法- 第K个语法符号

题目

在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始）
例子:

输入: N = 1, K = 1
输出: 0

输入: N = 2, K = 1
输出: 0

输入: N = 2, K = 2
输出: 1

输入: N = 4, K = 5
输出: 1

解释:
第一行: 0
第二行: 01
第三行: 0110
第四行: 01101001

思考和分析

看到这道题的第一反应是，拿到第N行的序数，然后遍历这个序数就ok了。
但是仔细一想，感觉这样做的复杂度有点高，需要解决两个小问题。

• 第N行的序数如何去遍历？因为参数是个整型，所以要遍历N的序数不太好操作。
• 因为要生成第N行的序数，就需要生成N行之前所有行的序数，代价有点大。

所以感觉第一反应不靠谱，并且很难解决。

因为每一行的序数生成，都是依托上一层的。那就画下来这个生成的过程。（😂😂画的非常丑）

图1.png

从图上能够看到，第四行的偶数位置（从1开始算）和第三行的每个数是正好相反的。第四行的奇数位置（从1开始算）和第三行的每个数是正好相同的。

因此，我们可以推理出以下的查找方式：

• 第四行的第k位置是奇数，那就找第三行的第m = (k+1)/2位置的数，要知道第三行m位置的数，就去找第二行(m+1)/2 ……
• 第四行的第k位置是偶数，那就找第三行的第m = k/2位置的数，要知道第三行m位置的数，就去找第二行m/2 ……，找到确切的0和1后，进行取反就可以了。

所以我们可以用递归的方式来解决这道题。下面是python代码：

class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
        if K == 1:
            return 0
        if N==2 and K==2:
            return 1
        if K%2 == 0:#偶数
            temp = self.kthGrammar(N-1,K//2)
            if temp:
                return 0
            else :
                return 1
        else:#奇数
            return self.kthGrammar(N-1,(K+1)//2)