1545. 找出第 N 个二进制字符串中的第 K 位

🟠   🔖  递归 字符串 模拟  🔗 力扣 LeetCode

题目

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)) for i > 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
};