JZX轻语：简

LeetCode 779 - 第K个语法符号

发表于2024年04月26日

数组规律题，可以通过列举前面几层得出规律：0 -> 0,1 -> 0,1,1,0 -> 0,1,1,0,1,0,0,1 -> 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0。每一层的长度都是上一层长度的两倍(一个数分裂出两个数)，且前半段即上一层数组，后半段是前半段的取反。令k从0开始计数，因此，第k位的取值，是第k - int(sqrt(k)) * 2位（即，获取前半段的对应位，去掉最高位的1即可）的值的取反。进一步地，如果k位串中1的计数为奇数，则最终结果为1，否则为0。

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        return (k - 1).bit_count() % 2