与非的谜题
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 392 ms, 内存: 22.1 MB
/* 思路:
* 1. 初始化谜题数组 arr 和操作列表 operations。
* 2. 使用 Java Stream 对操作列表进行遍历和处理。
* 3. 若为修改操作(type = 0),则修改 arr 中相应位置的值。
* 4. 若为运算操作(type = 1),则对给定数字 y 进行 x*n 次「与非」运算,得到运算结果。
* 5. 将所有运算结果进行异或运算,得到最终密码。
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public class Solution {
public int finalPassword(int k, int[] arr, int[][] operations) {
int n = arr.length;
return Arrays.stream(operations).reduce(0, (result, op) -> {
if (op[0] == 0) {
// 修改操作
arr[op[1]] = op[2];
return result;
} else if (op[0] == 1) {
// 运算操作
int x = op[1];
int y = op[2];
for (int i = 0; i < x * n; i++) {
y = ~(y & arr[i % n]);
}
return result ^ y;
}
return result;
}, (a, b) -> a ^ b);
}
}
解释
方法:
这道题的题解采用了线段树(segment tree)的数据结构来高效地处理数组中的与非(NAND)运算。首先,构造一个线段树,其中每个节点代表一个区间的与非运算结果。线段树的大小是2倍的最接近n的2的幂的大小。在构造过程中,每个叶子节点存储与非运算的初始结果,而内部节点存储子区间的与非运算结果。接着,对于每个操作,如果是修改操作(type=0),则更新线段树中相应的叶子节点,并向上更新所有影响到的内部节点。如果是运算操作(type=1),则根据运算次数的奇偶性,从根节点开始计算与非运算的结果,并将结果异或到最终答案中。
时间复杂度:
O(n + m log n)
空间复杂度:
O(n)
代码细节讲解
🦆
题解中提到构造线段树时,每个节点代表区间的与非运算结果,这种表示方法如何确保能正确反映数组中元素的与非运算结果?
▷🦆
在更新线段树的叶子节点后,如何确保向上更新所有影响到的内部节点的过程是正确的?具体是如何处理这些节点的?
▷🦆
题解中提到根据运算次数的奇偶性来计算与非运算的结果,这种方法的逻辑基础是什么?为什么要依赖于奇偶性?
▷