Java 中查找 N 个二进制字符串中的第 K 位

问题陈述

给定两个整数 n 和 k。该问题生成一个序列，其中每个 S_n 是根据前一个字符串递归形成的。转换遵循以下模式

• S1 = "0"
• S_n = S_n−1 + "1" + reverse(invert(Sn−1))

其中

• 反转 (Reverse)：颠倒字符顺序。
• 反转 (Invert)：将 '0' 变为 '1'，将 '1' 变为 '0'。

由于字符串的指数级增长，任务是在不显式构建整个 字符串 的情况下找到 S_n 中的第 k 位。

示例 1

输入: n = 4, k = 11

输出 1

解释: S₄ = "011100110110001"，第 11 位是 '1'。它映射到 S₃ 中的位置 5 并被反转。

示例 2

输入: n = 2, k = 3

输出 1

解释: S₂ = "0110"，第 3 位是 '1'。由于 3 是中间位置，我们返回 '1'。

方法 1：递归模拟方法

该方法递归地执行，而不显式构建整个字符串 S_n。它生成序列；我们根据转换的递归属性来确定 k 的位置。

算法

步骤 1: 如果 n=1，返回 '0'，因为 S1 = "0"。

步骤 2: S_n 的长度为 (2ⁿ−1)。

步骤 3: 中间位始终位于位置 (length/2) + 1 处，并且是 '1'。

步骤 4: 如果 k 在左半部分 (k < mid)，它与 S_n−1 相同。

步骤 5: 如果 k 在右半部分 (k > mid)，它映射到 S_n−1 中的 (length – k + 1) 位置，但被反转。

步骤 6: 求解新的映射索引。

让我们在 Java 程序中实现上述步骤。

输出

 
1   

复杂度

时间复杂度: 程序的 O(n)。这是因为每次递归调用都会将 n 减 1，导致最多进行 n 次递归调用。

空间复杂度: 程序的 O(n)。这是因为递归函数调用存储在调用栈中。