【leetcode】K-th Symbol in Grammar

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目如下：

解题思路：直接把每行的数据计算出来肯定是不行的，因为N最大是30，那个第N行长度就是2^30次方，这显然不可取。那么就只能找规律了，我采取的是倒推法。例如假如我们要求出第四行第七个元素的值，记为[4,7]，显然[4,7]是从第三行的第四个元素计算得来的[3,4]，依次类推接下来是[2,2] ，[1,1] 。这样就形成了一个[4,7] -> [3,4] ->[2,2] -> [1,1]递推链。而[1,1]的值是确定的就是0，那么[2,2]就是0转换成01的第二个元素1，[3,4]就是1转换成10的第二个元素0，[4,7]就是0转换后01的第一个元素0。

完整代码如下：

class Solution(object):

    def kthGrammar(self, N, K):

        """

        :type N: int

        :type K: int

        :rtype: int

        """

        chain = []

        t = N

        p = K

        while t >= 1:

            chain.insert(0,p)

            p = p /2 + p%2

            t -= 1

        print chain

        value0 = [0,1]

        value1 = [1,0]

        v = 0

        for i in range(1,len(chain)):

            if chain[i] % 2 == 0 and v == 0:

                v = value0[1]

            elif chain[i] % 2 == 1 and v == 0:

                v = value0[0]

            elif chain[i] % 2 == 0 and v == 1:

                v = value1[1]

            elif chain[i] % 2 == 1 and v == 1:

                v = value1[0]

        return v