LeetCode每日一题——779. 第K个语法符号
LeetCode每日一题系列
题目：779. 第K个语法符号 难度：普通
题目
我们构建了一个包含 n 行( 索引从 1 开始 )的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。
例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。 给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）
示例
示例 1:
输入: n = 1, k = 1 输出: 0 解释: 第一行：0
示例 2:
输入: n = 2, k = 1 输出: 0 解释: 第一行: 0 第二行: 01
示例 3:
输入: n = 2, k = 2 输出: 1 解释: 第一行: 0 第二行: 01
提示:
1 <= n <= 30 1 <= k <= 2n - 1
思路
假如每个序列就是把一个0-indexed的，且转换关系为0-01和1-10，那么我们发现奇数位的数字永远和上一行对应的数字不同，那么就需要找到翻转了多少次，翻转奇数次则为1，偶数次为0（未翻转），，上一行的idx位置在下一行的（idx<<1）处相同，在（(idx<<1)+1）处不同，那么本质就是计算（k-1）的比特数的奇偶
题解
class Solution:
def kthGrammar(self, n: int, k: int) -> int:
return bin(k-1).count(1)&1
