我遇到了这个问题，其中给出了所有程序，只排除了一段逻辑。下列问题的空行可以填什么？
问题陈述
jack 和丹尼尔是 friend 。 他们想加密他们的谈话，这样他们就可以避免被侦探机构拦截。所以他们发明了一种新的密码。 每条消息都被编码为长度为 N 的二进制表示形式 B。 然后它被写下 K 次，移动 0,1,...,K−1 位。 如果 B=1001010 和 K=4 它看起来像:
1001010
1001010
1001010
1001010
然后计算每一列的异或并记下来。这个数字叫做 S。例如，对上述示例中的数字进行异或运算会导致
1110100110
然后将编码后的消息 S 和 K 发送给 Daniel。
Jack 正在使用这个编码算法，并要求Daniel 实现一个解码算法。你能帮助丹尼尔实现这个吗？
输入格式
- 第一行包含两个整数N和K。
- 第二行包含长度为 N+K−1 的字符串 S，由 1 和 0 组成。
输出格式
长度为 N 的解码消息，由 1 和 0 组成。
约束
- 1≤N≤10^6,
- 1≤K≤10^6
- |S|=N+K−1
- 保证S是正确的。
示例输入#00
7 4
1110100110
示例输出#00
1001010
示例输入#01
6 2
1110001
示例输出#01
101111
输入#00的解释
1001010
1001010
1001010
1001010
----------
1110100110
解释输入#01
101111
101111
-------
1110001
import java.io.*;
public class Solution {
public static void solve(Input in, PrintWriter out) throws IOException {
int n = in.nextInt();
int k = in.nextInt();
char[] c = in.next().toCharArray();
int x = 0;
char[] ans = new char[n];
for (int i = 0; i < n; ++i) {
ans[i] = (char) (((c[i] - '0') ^ x) + '0');// I understand we are converting the character into integer (c[i] - '0') then xoring it with x which is holding 0 and then again adding '0' to convert back it into character.
x ^= ans[i] - '0';// But why are we doing this!!. From this line onward things are not clear.
if (i >= k - 1) {
****FILL THE MISSING LINE HERE****
}
}
out.println(ans);
}
public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(System.out);
solve(new Input(new BufferedReader(new InputStreamReader(System.in))), out);
out.close();
}
static class Input {
BufferedReader in;
StringBuilder sb = new StringBuilder();
public Input(BufferedReader in) {
this.in = in;
}
public Input(String s) {
this.in = new BufferedReader(new StringReader(s));
}
public String next() throws IOException {
sb.setLength(0);
while (true) {
int c = in.read();
if (c == -1) {
return null;
}
if (" \n\r\t".indexOf(c) == -1) {
sb.append((char)c);
break;
}
}
while (true) {
int c = in.read();
if (c == -1 || " \n\r\t".indexOf(c) != -1) {
break;
}
sb.append((char)c);
}
return sb.toString();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
}
}
最佳答案
注意:请阅读解释，简单地通过复制粘贴答案来解决挑战是没有用的。
你可以利用的约束是
The first bit is untouched by the encryption algorithm.
确实是因为所有“掩码”都至少向右移动了一个。因此，您可以假设加密部分的第一位也是解密内容的第一位。
现在您知道了第一位，您可以轻松地重构第二位，因为它只是与我们已知的第一位进行异或运算。所以知道我们可以计算出第二个。
第三位与第一位和第二位异或，所以基本上做的是维护一个值，该值是所有已经获得的值的异或，并将其与下一个值异或。最初该值为零。
示例:
获取第一个样本输入:
1110100110
我们可以得出第一位是1。所以现在我们知道第二位的掩码的形式是:
1110100110
mask 1????????
result 10
现在我们知道第三位的掩码是 1 和 0 的异或，因此 1。
1110100110
mask 11???????
result 100
迭代最终会导致:
index 0123456789
data 1110100110
submasks 1001010
1001010
1001010
mask 0111??????
result 1001??????
现在在 k-1 次迭代之后，不再有额外的子掩码，事实上:一个只写 k 次数据作为结果，而 k-1 次子掩码。所以现在我们不再对新数据进行异或:我们只对结果的最后 k 位进行异或，这可以通过 unxoring (或简单地 xoring ) 结果的 k 个位向左。
对于下一个掩码，我们因此异或我们的状态(掩码的最后一位)与结果的最后一位(1)和结果 (1) 表示状态保持不变 (1):
index 0123456789
data 1110100110
submasks 1001010
1001010
1001010
mask 01111?????
result 10010?????
现在我们对最后一个结果位 (0) 和第二个结果位 (0) 进行异或:
index 0123456789
data 1110100110
submasks 1001010
1001010
1001010
mask 011111????
result 100101????
对于下一个，我们与最后一个 (1) 和第三个 (0) 进行异或，因此我们交换了状态。通过继续执行此过程，我们最终以:
index 0123456789
data 1110100110
submasks 1001010
1001010
1001010
mask 0111110???
result 1001010???
现在我们不再对剩余的位感兴趣，所以我们终止。
必须修改什么？
在if部分，我们需要xor (^) 与i-(k-1)-th 位也是:
if (i >= k - 1) {
x ^= ans[i-(k-1)] - '0';
}
关于Java异或运算，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30295342/