1545. 找出第 N 个二进制字符串中的第 K 位
1545. 找出第 N 个二进制字符串中的第 K 位
题目
Given two positive integers n
and k
, the binary string Sn
is formed as follows:
S1 = "0"
Si = Si - 1 + "1" + reverse(invert(Si - 1))
fori > 1
Where +
denotes the concatenation operation, reverse(x)
returns the reversed string x
, and invert(x)
inverts all the bits in x
(0
changes to 1
and 1
changes to 0
).
For example, the first four strings in the above sequence are:
S1 = "0"
S2 = "011"
S3 = "0111001"
S4 = "011100110110001"
Return the kth
bit in Sn
. It is guaranteed that k
is valid for the given n
.
Example 1:
Input: n = 3, k = 1
Output: "0"
Explanation: S3 is "0 111001".
The 1st bit is "0".
Example 2:
Input: n = 4, k = 11
Output: "1"
Explanation: S4 is "0111001101** 1** 0001".
The 11th bit is "1".
Constraints:
1 <= n <= 20
1 <= k <= 2^n - 1
题目大意
给你两个正整数 n
和 k
,二进制字符串 Sn
的形成规则如下:
S1 = "0"
- 当
i > 1
时,Si = Si-1 + "1" + reverse(invert(Si-1))
其中 +
表示串联操作,reverse(x)
返回反转 x
后得到的字符串,而 invert(x)
则会翻转 x 中的每一位(0 变为 1,而 1 变为 0)。
例如,符合上述描述的序列的前 4 个字符串依次是:
S1 = "0"
S2 = "011"
S3 = "0111001"
S4 = "011100110110001"
请你返回 Sn
的 第k
位字符 ,题目数据保证 k
一定在 Sn
长度范围以内。
提示:
1 <= n <= 20
1 <= k <= 2^n - 1
解题思路
可以使用递归方法生成第
n
个二进制字符串。生成的过程可以用S(n) = S(n-1) + '1' + reverse(invert(Si - 1))
来表示,其中reverse
是翻转操作,invert
是取反操作,通过split
和map
方法实现取反操作。一旦生成了第
n
个字符串,就可以根据 1-indexed 规则返回第k
位的字符。
复杂度分析
- 时间复杂度:
O(2^n)
,随着n
增加,字符串长度呈指数增长。 - 空间复杂度:
O(2^n)
,存储生成的字符串所需的空间。
代码
/**
* @param {number} n
* @param {number} k
* @return {character}
*/
var findKthBit = function (n, k) {
const genString = (n) => {
if (n == 1) return '0';
const prev = genString(n - 1);
const reverse = prev
.split('')
.map((i) => (i == '0' ? '1' : '0'))
.reverse()
.join('');
return prev + '1' + reverse;
};
const str = genString(n);
return str[k - 1]; // k 是 1-indexed
};