盛日辉的博客
0%

Leetcode 3845. 最大子数组异或值（01字典树、单调队列）

发表于 更新于 分类于

题目：3845. 最大子数组异或值

0-1 字典树（异或字典树）

这个如果了解异或字典树就不算难，可惜我比赛的时候没有想到。直接贴代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class TrieNode:
    __slots__ = 'children', 'cnt'

    def __init__(self):
        self.children = [None, None]
        self.cnt = 0


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, x):
        node = self.root
        for i in range(15, -1, -1):
            b = (x >> i) & 1
            if not node.children[b]:
                node.children[b] = TrieNode()
            node.children[b].cnt += 1
            node = node.children[b]

    def delete(self, x):
        node = self.root
        for i in range(15, -1, -1):
            b = (x >> i) & 1
            node = node.children[b]
            node.cnt -= 1

    def query(self, x):
        node = self.root
        res = 0
        for i in range(15, -1, -1):
            b = (x >> i) & 1
            bb = 1 - b
            if node.children[bb] and node.children[bb].cnt > 0:
                # 可以取 1
                res |= 1 << i
                node = node.children[1 - b]
            else:
                # 这一位只能同 x，res 取 0
                node = node.children[b]
        return res


class Solution:
    def maxXor(self, nums: list[int], k: int) -> int:
        min_q = deque()
        max_q = deque()
        xor_sum = [0]
        for x in nums:
            xor_sum.append(xor_sum[-1] ^ x)
        ans = 0
        left = 0
        trie = Trie()
        trie.insert(0)
        for right, x in enumerate(nums):
            trie.insert(xor_sum[right + 1])
            while max_q and nums[max_q[-1]] <= x:
                max_q.pop()
            max_q.append(right)
            while min_q and nums[min_q[-1]] >= x:
                min_q.pop()
            min_q.append(right)

            while nums[max_q[0]] - nums[min_q[0]] > k:
                trie.delete(xor_sum[left])
                left += 1
                if left > max_q[0]:
                    max_q.popleft()
                if left > min_q[0]:
                    min_q.popleft()

            ans = max(ans, trie.query(xor_sum[right + 1]))
        return ans

说明一点单调队列里的一个小点。

while max_q and nums[max_q[-1]] <= x: 和 while min_q and nums[min_q[-1]] >= x: 的等号的作用：

  • 代码简洁，如果不加的的话在出队的时候，两个 if left > 要写成 while；
  • 空间复杂度更好。

附两个单调队列的题：

421. 数组中两个数的最大异或值 也可以练习0-1字典树（这题也可以不用）。

试填法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# 试填法
class Solution:
    def maxXor(self, nums: list[int], k: int) -> int:
        # 1. 预处理 lefts[r] = l 表示 r 作为右端点符合最大值最小值条件的最远的左端点是 l
        n = len(nums)
        lefts = [0] * n
        min_q = deque()
        max_q = deque()
        left = 0
        mx = 0  # 最大值
        pre = [0]  # 前缀异或和
        for right, x in enumerate(nums):
            if x > mx:
                mx = x
            pre.append(x ^ pre[-1])
            while max_q and x >= nums[max_q[-1]]:
                max_q.pop()
            max_q.append(right)
            while min_q and x <= nums[min_q[-1]]:
                min_q.pop()
            min_q.append(right)
            while nums[max_q[0]] - nums[min_q[0]] > k:
                left += 1
                if left > max_q[0]:
                    max_q.popleft()
                if left > min_q[0]:
                    min_q.popleft()
            lefts[right] = left

        # 2. 试填法
        ans = 0
        width = mx.bit_length()
        for i in range(width - 1, -1, -1):
            # 假设第 i 位是 1
            ans = (ans << 1) | 1  # 目前只有高位（第 i 位及高位）
            # 目前的位数为 width - i，对应有 1 << (width - i) 种情况
            # last[s] 记录 s **在 pre 数组中** 上一次出现的位置 
            last = [-1] * (1 << (width - i))
            last[0] = 0
            for r in range(n):
                # 计算前缀异或和与 ans 异或的结果（只看第 i 位及高位）
                # 如果结果在之前出现过（last[结果[ != -1）且在 [lefts[r]， r] 之间
                # 说明这一位可以是 1
                s = pre[r + 1] >> i
                if last[s ^ ans] >= lefts[r]:
                    break
                # 因为是 pre 中的位置，所以 + 1
                last[s] = r + 1
            else:
                ans -= 1  # 第 i 位填 0
        return ans