跳至主要內容

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


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

🟠   🔖  递归 字符串 模拟  🔗 力扣open in new window LeetCodeopen in new window

题目

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

题目大意

给你两个正整数 nk,二进制字符串 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"

请你返回 Snk 位字符 ,题目数据保证 k 一定在 Sn 长度范围以内。

提示:

  • 1 <= n <= 20
  • 1 <= k <= 2^n - 1

解题思路

  • 可以使用递归方法生成第 n 个二进制字符串。生成的过程可以用 S(n) = S(n-1) + '1' + reverse(invert(Si - 1)) 来表示,其中 reverse 是翻转操作,invert 是取反操作,通过 splitmap 方法实现取反操作。

  • 一旦生成了第 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
};