跳转至

LeetCode: 779. 第K个语法符号

1、题目描述

在第一行我们写上一个 0。接下来的每一行,将前一行中的0替换为011替换为10

给定行数 N 和序数 K,返回第 N 行中第 K个字符。(K1开始)

例子:

输入: N = 1, K = 1
输出: 0

输入: N = 2, K = 1
输出: 0

输入: N = 2, K = 2
输出: 1

输入: N = 4, K = 5
输出: 1

解释:
第一行: 0
第二行: 01
第三行: 0110
第四行: 01101001

注意:

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

2、解题思路

  • 直接计算法
0
01
0110
0110 1001
0110 1001 1001 0110
0110 1001 1001 0110 1001 0110 0110 1001
0110 1001 1001 0110 1001 0110 0110 1001 1001 0110 0110 1001 0110 1001 1001 0110

实际上是有规律的,上面的后一行的前半部分与前面相同,后半部分则是前面的取反

因此,直接不断的一半一半的截取,截取到前面即可,需要注意的是当前值是否需要取反

class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
        line_four = [0, 1, 1, 0, 1, 0, 0, 1]

        if K <= 8:
            return line_four[K - 1]

        flag = True
        for i in range(N - 2, 1, -1):
            if K > 2 ** i:
                K -= 2 ** i
                flag = not flag

        if flag:
            return line_four[K - 1]
        else:

            return 0 if line_four[K - 1] else 1