leetcode
leetcode 3051 ~ 3100
与非的谜题

与非的谜题

难度:

标签:

题目描述

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)

代码细节讲解

🦆
题解中提到构造线段树时,每个节点代表区间的与非运算结果,这种表示方法如何确保能正确反映数组中元素的与非运算结果?
在线段树中,每个节点的值是根据其子节点的值通过特定的逻辑运算(此处为与非运算)计算得到的。与非运算是对其子区间内的所有元素进行的逐对逻辑运算。通过递归地将叶子节点(即原始数组元素)的与非结果合并,每个内部节点最终会反映出其所代表的子区间内所有元素的与非结果。这种自底向上的构建方法确保了从叶子节点到根节点,每个节点的值都精确地代表了对应区间内的运算结果。
🦆
在更新线段树的叶子节点后,如何确保向上更新所有影响到的内部节点的过程是正确的?具体是如何处理这些节点的?
当线段树的叶子节点发生更新时,影响会向上传播至根节点。具体来说,首先更新受影响的叶子节点,然后逐级向上更新其父节点。每个父节点的新值根据其两个子节点的值通过与非运算重新计算得出。这个更新过程重复进行,直到达到根节点。通过这种方式,可以确保所有受影响的内部节点的值都会被正确地更新,从而保持整个线段树的一致性和正确性。
🦆
题解中提到根据运算次数的奇偶性来计算与非运算的结果,这种方法的逻辑基础是什么?为什么要依赖于奇偶性?
与非运算的结果可能会随着运算次数的增加而变化,特别是在多次连续运算的情况下。在题解中,奇偶性的考虑基于与非运算的性质,即重复的与非运算可能会在一定的结果之间周期性地变化(例如,可能在两个特定的值之间切换)。因此,通过考虑运算次数的奇偶性,可以决定采用哪种计算模式,从而优化运算过程,避免不必要的重复计算。这种方法基于对运算结果周期性变化的观察和利用,是一种有效利用已有信息进行优化的策略。

相关问题