1545. Find Kth Bit in Nth Binary String¶
题目信息¶
- 题号:
1545
- 难度:
Medium
- 主题:
递归、二进制字符串、对称性
- 原题:
- 重点:
S1 = 0,Sn = S(n-1) + 1 + reverse(invert(S(n-1)));返回一基位置k的字符
题目重述¶
定义二进制字符串序列:S1 = "0";对于 n > 1,Sn 等于 S(n-1)、字符 1 和 S(n-1) 按位取反后再反转的结果依次连接。
给定 n 和一基下标 k,请返回 Sn 的第 k 个字符。
1 <= n <= 20,1 <= k <= 2^n - 1。
自建示例¶
目标位置可能位于反转取反后的右半部分:
输入:n = 3, k = 5
输出:"0"
解释:S3 为 "0111001",第五个字符是 0。
基础字符串只有一个字符:
输入:n = 1, k = 1
输出:"0"
解释:S1 定义为 "0"。