1545. Find Kth Bit in Nth Binary String

题目信息

题号:

1545

难度:

Medium

主题:

递归、二进制字符串、对称性

原题:

LeetCode 1545

重点:

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"。