0779. K-th Symbol in Grammar

题目信息

题号:

0779

难度:

Medium

主题:

递推序列、二进制、下标

原题:

LeetCode 0779

重点:

行号与位置都从 1 开始;第一行为 0,之后每个 0 生成 01、每个 1 生成 10,返回第 n 行第 k 个符号

题目重述

构造一个按行编号的二进制表。第 1 行只有字符 0。生成下一行时,将上一行中的每个 0 替换为 01,每个 1 替换为 10,并按原顺序拼接。

给定整数 n 和 k,请返回第 n 行中第 k 个符号。行号和位置都使用从 1 开始的编号。

1 <= n <= 30,并且 1 <= k <= 2^(n - 1)。

自建示例

查询较深一行中的位置:

输入:n = 5, k = 11
输出:0
解释:第 5 行为 "0110100110010110",从 1 开始计数的第 11 个字符是 0。

查询一行允许的最后一个位置:

输入:n = 3, k = 4
输出:0
解释:第 3 行为 "0110",其长度为 ``2^(3 - 1) = 4``。``k = 4`` 取到该行允许的最大位置,最后一个符号是 0。