779. K-th Symbol in Grammar

题目

大概的意思就是形成一个N层的序列，就像
0
01
0110
01101001
我们可以发现前半部分它们完全相同，后半部分是前半部分求反的结果。
但碍于对于位运算的不理解，并没有得出代码，于是查看讨论区。

高效代码

class Solution(object):
    def kthGrammar(self, N, K):
        """
        :type N: int
        :type K: int
        :rtype: int
        """
        return bin(K-1).count('1')%2

高效代码二

逐层分解法。

class Solution:
    def kthGrammar(self, N, K):
        if N == 1:
            if K == 1:
                return 0
            else:
                return 1

        half = 2**(N - 1)
        print("half", N, K, half)
        if K <= half:
            return self.kthGrammar(N - 1, K)
        else:
            res = self.kthGrammar(N - 1, K - half)
            if res == 0:
                return 1
            else:
                return 0