题目描述：

LeetCode 779. K-th Symbol in Grammar

On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.

Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).

Examples:
Input: N = 1, K = 1
Output: 0

Input: N = 2, K = 1
Output: 0

Input: N = 2, K = 2
Output: 1

Input: N = 4, K = 5
Output: 1

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

Note:

1. N will be an integer in the range [1, 30].
2. K will be an integer in the range [1, 2^(N-1)].

题目大意：

第一行写一个0，接下来的每一行，都把上一行的0换成01，把1换成10

求第N行第K列的数字。

解题思路：

递归（Recursion）

详见代码。

Python代码：

class Solution(object):
    def kthGrammar(self, N, K):
        """
        :type N: int
        :type K: int
        :rtype: int
        """
        if N == 1: return 0
        if K == 2: return 1
        if K <= 1 << N - 2: return self.kthGrammar(N - 1, K)
        K -= 1 << N - 2
        return 1 - self.kthGrammar(N - 1, K)

 

本文链接：http://bookshadow.com/weblog/2018/02/04/leetcode-k-th-symbol-in-grammar/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码