查找 N 次迭代后获得的二进制字符串的第 k 个索引字符。在每次迭代中——“0”变成“10”，“1”变成“01”

Question

我正在尝试为给定场景确定解决方案（最好在 JAVA 中）：

输入：

二进制字符串：例如“1001”
N - 迭代次数
K - 字符串索引位置

每次迭代后，所有的1都变成“01”，0都变成“10” 例如

初始value/input --> "1001"
第一次迭代后 --> “01101001”
第二次迭代后 --> "1001011001101001"
...
...
第N次迭代后--> "100101011......[第K个索引值]......00101010111.."（这里我们的程序需要找到第 K 个索引值，它可以是 0 或 1)

输出： N 次迭代后第 k 个索引处的值（0 或 1）。

Answer 1

经过N次迭代，每个原始数字变成2^N个数字，所以跳过数字直到我们接近K。

例如对于输入 "1001"、N=3、K=20，第一个数字变成了 8 个数字，所以如果我们跳过这 8 个数字两次，即跳过 2 个原始数字 = 16 K，我们就在第3个原始数字（一个0），还有一个剩余的K=4.

然后我们对该数字应用迭代，得到 0 -> "10"。我们现在可以重新启动操作，输入 "10"、N=2、K=4.

重复直到完成。 O(N) 中的解决方案，无论输入长度或 K 的值如何。

当然，你可以直接暴力破解它，但在更高的值下效果不佳，因为解决方案是 O(L * 2^N)，其中 L 是输入长度。

// Brute-force solution
static char solve(String input, int n, int k) {
    String s = input;
    for (int i = 0; i < n; i++)
        s = s.chars().mapToObj(c -> c == '0' ? "10" : "01").collect(Collectors.joining());
    return s.charAt(k); // assuming k is 0-based
}

上述解决方案的精简版：

// Optimized solution
static char solve(String input, int n, int k) {
    for (; n > 0; k %= 1 << n--)
        input = input.charAt(k / (1 << n)) == '0' ? "10" : "01";
    return input.charAt(k);
}

查找 N 次迭代后获得的二进制字符串的第 k 个索引字符。在每次迭代中——“0”变成“10”，“1”变成“01”

Find k th index character of a binary string obtained after N iterations. In each iteration - '0' becomes '10' and '1' becomes '01'

java

algorithm

dynamic-programming

recursive-datastructures

data-structures