这个题目有点绕，其实很简单。

题目是一行都是只有0或者1两个元素，下一行是当前的转变，0的元素变为01，1的元素变为10。

举例如下，那么给出行数N，和横向位数K，那个元素是0还是1.

比如如下给出N是4，K是5，那个元素就是1。

Explanation:

row 1: 0 row 2: 01 row 3: 0110 row 4: 01101001

其实这个问题某种意义上就是简单版的帕斯卡三角，如果头铁一层一层递归下来当然可以，不过效率太低了。

分析了下，其实对于当前行的横向位数K，就是上一行向上取整K/2位的元素的转变过来的，如果上一个是0，则是0或者1，如果若非偶数，就是0，如果偶数就是1；对于1，非偶数则是1，偶数是0。按照这个道理递归即可。

代码如下，int((K+1)/2)是为了向上取整。

class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
        defuatN = 4
        defautRow = '01101001'
        if K < 8:
            return int(defautRow[K-1])
        else:
            if K%2 == 1:
                re = self.kthGrammar(N-1,int((K+1)/2))
            else:
                re = 0 if self.kthGrammar(N-1,int((K+1)/2)) == 1 else 1
            return re

ITPub博客

刷题系列 - K-th 语法

最新文章