java - 求n次变化后的第K位数字

Question

有一个变化规则，0 -> 01，1 -> 10。例如变化后，10 为 1001。

假设输入为0，这样的规则变化n次后，第K位是多少？

我只能给出残酷的解决方案，如下。不过我相信存在更好的解决方案，任何人都可以提出一些新的想法吗？

public char lalala(int n, int k) {
    String str = "0";
    for (int i = 0; i < n; i++) {
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < str.length; j++) {
            if (str.charAt(j) == '0') {
                sb.append("01");
            } else {
                sb.append("10");
            }
        }
        str = sb.toString();
    }
    return str.charAt(k);
}

Answer 1

所以你生成的字符串看起来像

0110100110010110....

现在让我们垂直书写这些数字并打印每个数字位置的二进制表示

value|position -> position binary
-----+---------------------------
0    | 0       -> 0000
1    | 1       -> 0001
1    | 2       -> 0010
0    | 3       -> 0011
1    | 4       -> 0100
0    | 5       -> 0101
0    | 6       -> 0110
1    | 7       -> 0111
.      .          ....
.      .          ....

如果你仔细观察，你会发现:

• 如果 position 的二进制表示中 1 的个数为偶数，value 为 0
• 如果 position 的二进制表示中 1 的个数为奇数，value 为 1

这意味着

0001、0010、0100、0111 包含奇数个 1 值将为1。

换句话说，值等于个数模2。

利用这一事实，您可以创建代码，将您的 n 转换为表示其二进制形式的字符串，对所有的求和，并检查它是奇数还是偶数。

将 n 转换为 value 的代码如下所示

public static int value(int n) {
    String binary = Integer.toBinaryString(n);
    return binary.chars().map(e -> e == '1' ? 1 : 0).sum() % 2;
}

(如果您不熟悉 Java 8 中引入的流，请使用更长的版本)

public static int value(Integer n) {
    String binary = Integer.toBinaryString(n);
    int count = 0;
    for (char ch : binary.toCharArray())
        if (ch == '1') count ++;
    return count % 2;
}

当你像这样使用它时

for (int i = 0; i < 20; i++)
    System.out.print(value(i));

您将得到输出01101001100101101001，这似乎是正确的。