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)``。 自建示例 -------- 查询较深一行中的位置: .. code-block:: text 输入:n = 5, k = 11 输出:0 解释:第 5 行为 "0110100110010110",从 1 开始计数的第 11 个字符是 0。 查询一行允许的最后一个位置: .. code-block:: text 输入:n = 3, k = 4 输出:0 解释:第 3 行为 "0110",其长度为 ``2^(3 - 1) = 4``。``k = 4`` 取到该行允许的最大位置,最后一个符号是 0。