779_medium_第K个语法符号.md

Leetcode 779 第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

提示：

1. N 的范围 [1, 30].
2. K 的范围 [1, 2^(N-1)].

考点

• 递归

思路

正常展开的话会超时。所以我们考虑递归方法。
画出满二叉树就好理解了，根据当前层位置的奇偶算出上一层的位置，最终一定会到达第一层的0，然后回溯得到当前层的上一层的值，根据本层的奇偶性判断本层的值，发现本层位置偶数位与父结点值相反，奇数位则相同即可确认本层值

代码1

执行用时: 52ms, 内存消耗: 13MB。

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

代码2（执行用时：52ms）

研究下结构，呈现对称-反转（0-1），很自然想到2进制表示，易见答案与K-1在二进制表示下的1的个数的奇偶性有关。

class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
      
        res = 0
        K -= 1
        while K:
            res += K % 2
            K = K >> 1
        return res % 2