0779. K-th Symbol in Grammar¶
题目信息¶
- 题号:
0779
- 难度:
Medium
- 主题:
递推序列、二进制、下标
- 原题:
- 重点:
行号与位置都从 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。