算法leetcode

力扣1707-与数组中元素的最大异或值

字数统计: 1.5k字   |   阅读时长: 7分
, , ,

摘要: 用 01Trie 处理 01 串的统计问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们看一个 01Trie 的应用的问题，统计 01 串上的某些信息。比经典 01Trie 在节点上新增了额外维护某些统计信息的字段。查询时可以离线查询也可以在线查询。

$1 题目

给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [xi, mi] 。

第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR xi) ，其中所有 j 均满足 nums[j] <= mi 。如果 nums 中的所有元素都大于 mi，最终答案就是 -1 。

返回一个整数数组 answer 作为查询的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 个查询的答案。

1
2
3
4
提示：
1 <= nums.length, queries.length <= 1e5
queries[i].length == 2
0 <= nums[j], xi, mi <= 1e9

示例 1：
输入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
输出：[3,3,7]
解释：
1) 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.

示例 2：
输入：nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
输出：[15,-1,5]

$2 题解

如果没有不超过 mi 这个限制条件，问题就变成了给定 xi 求最大异或值，这是一个利用 01Trie 解决的基本问题，可以参考 01Trie 这篇文章。

算法: 01Trie + 离线查询

直接给定了所有查询的问题，可以利用离线的思想，即合理地调整回答查询的顺序，达到降低时间复杂度的目的。

将 nums 所有数字排序，然后将查询 q = (x, m) 按 m 从小到大排序。

枚举查询 qi = (xi, mi)，首先将 nums 中小于等于 mi 的数都插入 01Trie，这个过程可以维护一个 nums 上的指针，只插入该指针之后的部分就可以。插入完成后后，此时 xi 与 01Trie 中已插入的数字的最大异或值就是该查询的答案。

代码 (C++)

注意: 以下代码如果将字典树定义 Trie01 *trie = Trie01() 改为Trie01 trie，并将 trie01 -> insert() 和 trie01 -> search()改为 trie01.insert() 和trie01.search()，则运行时间会并超时，经测试增加 4 倍。

字典树直接使用 01Trie 中的模板。

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
struct Query
{
    int idx;
    int xi;
    int mi;
    Query(int i, int xi, int mi):idx(i),xi(xi),mi(mi){}
    bool operator<(const Query& q) const
    {
        return mi < q.mi;
    }
};

class Solution {
public:
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        int m = queries.size();
        sort(nums.begin(), nums.end());
        vector<Query> qs;
        for(int i = 0; i < m; ++i)
            qs.emplace_back(i, queries[i][0], queries[i][1]);
        sort(qs.begin(), qs.end());
        Trie01 *trie01 = new Trie01();
        vector<int> result(m);
        int iter = 0;
        for(int j = 0; j < m; ++j)
        {
            while(iter < n && nums[iter] <= qs[j].mi)
            {
                trie01 -> insert(nums[iter]);
                ++iter;
            }
            result[qs[j].idx] = trie01 -> search(qs[j].xi);
        }
        return result;
    }
};

算法: 01Trie + 在线查询

在常规 01Trie 的基础上，给节点增加一个 minx 字段，表示以该节点为根的子树上的数字的最小值。这个信息在在线处理查询时需要用到。

首先将所有数字都插入 01Trie，然后依次处理每个查询。

对每个查询 q[i] = (xi, mi)，在建好的 Trie01 中找与 xi 异或最大的值。过程如下：

1
2
3
4
5
6
从根开始向叶子走，用 iter 维护走的过程
当前 iter 应该始终是保证 iter -> minx <= mi 的，此时需要判断 iter 应该往哪个方向走
若 xi 的当前位为 1:
    则在最好走左子树: 存在左子树就走左子树，否则走右子树
若 xi 的当前位为 0:
    则在最好走右子树: 存在右子树，且右子树的最小值 <= mi，则走右子树，否则走左子树

代码 (C++)

Trie01 在常规模板的基础上需要做一些修改，代码如下：

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
struct Trie01Node
{
    Trie01Node *left, *right;
    int minx;
    Trie01Node(int minx=INT_MAX)
    {
        left = nullptr, right = nullptr;
        this -> minx = minx;
    }
    ~Trie01Node(){}
};

class Trie01
{
public:
    Trie01()
    {
        root = new Trie01Node();
    }

    ~Trie01()
    {
        if(root)
        {
            delete_subtree(root);
        }
    }

    void insert(int num)
    {
        Trie01Node *iter = root;
        iter -> minx = min(iter -> minx, num);
        // 从高位到低位枚举
        for(int i = 30; i >= 0; --i)
        {
            if((num >> i) & 1)
            {
                if(!iter -> right)
                    iter -> right = new Trie01Node();
                iter = iter -> right;
            }
            else
            {
                if(!iter -> left)
                    iter -> left = new Trie01Node();
                iter = iter -> left;
            }
            iter -> minx = min(iter -> minx, num);
        }
    }

    bool empty() const
    {
        if(!root)
            return true;
        if(!root -> left && !root -> right)
            return true;
        return false;
    }

    int search(int x, int mi)
    {
        if(empty())
            return -1;
        /*
         * 给定 x，找到使得 x ^ a 最大的 a
         * 尽可能让高位上的 x 与 a 不同
         * 所有的数都是长度 30 捅到底的
         */
        Trie01Node *iter = root;
        if(iter -> minx > mi)
            return -1;
        int a = 0;
        for(int i = 30; i >= 0; --i)
        {
            if((x >> i) & 1)
            {
                if(iter -> left)
                    iter = iter -> left;
                else
                {
                    iter = iter -> right;
                    a |= (1 << i);
                }
            }
            else
            {
                if(iter -> right && iter -> right -> minx <= mi)
                {
                    iter = iter -> right;
                    a |= (1 << i);
                }
                else
                    iter = iter -> left;
            }
        }
        return a ^ x;
    }

private:
    Trie01Node *root;

    void delete_subtree(Trie01Node* node)
    {
        if(node -> left)
            delete_subtree(node -> left);
        if(node -> right)
            delete_subtree(node -> right);
        delete node;
        node = nullptr;
    }
};

class Solution {
public:
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        int m = queries.size();
        Trie01 *trie01 = new Trie01();
        for(int x: nums) trie01 -> insert(x);
        vector<int> result(m);
        for(int i = 0; i < m; ++i)
        {
            result[i] = trie01 -> search(queries[i][0], queries[i][1]);
        }
        return result;
    }
};
Share