题目
在第一行我们写上一个 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)
