这道题用Trie + DFS来做,代码模板参照143. 最大异或对 - AcWing题库
查询过程中分别对每层的 !u 和 u 节点尝试DFS,如果不存在trie向下的路径或当前值大于mi则放弃。
const int M = 30, N = M * 1e5 + 10;
class Solution {
public:
int son[N][2], cnt[N], idx = 0;
void insert(int x){
int p = 0;
for (int i = M; i>=0; i--){
int u = x >> i & 1;
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] = x;
}
int dfs(int i, int &x, int &y, int p, bool flag){
if (i == -1)
return cnt[p];
int u = x >> i & 1, v = y >> i & 1;
int arr[] = {!u, u};
for (int t = 0; t < 2; t++){
int target = arr[t];
if (!son[p][target] ||
(!flag && target > v)) continue;
if (target < v) flag = true;
int ret = dfs(i-1, x, y, son[p][target], flag);
if (ret != -1) return ret;
}
return -1;
}
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
memset(son, 0, sizeof son);
memset(cnt, 0, sizeof cnt);
for (auto &x : nums) insert(x);
vector<int> ans;
for (auto &p : queries){
int ret = dfs(M, p[0], p[1], 0, false);
ans.push_back(ret == - 1 ? -1 : p[0] ^ ret);
}
return ans;
}
};