【Day27】1707.与数组中元素的最大异或值

1707. 与数组中元素的最大异或值

给你一个由非负整数组成的数组 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:

输入: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]

提示:

  • 1 <= nums.length, queries.length <= 105
  • queries[i].length == 2
  • 0 <= nums[j], xi, mi <= 109

题解:

const int N = 1e5 + 50, M = 32 * N;
int son[M][2];
int idx;

void insert(int x){
    int p = 0;
    for(int i = 31; i >= 0; i--){
        int u = (x >> i) & 1;
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
}
int query(int x){
    int ans = 0, p = 0;
    for(int i = 31; i >= 0; i--){
        int u = (x >> i) & 1;
        if(son[p][!u]) {
            ans += (1 << i);
            p = son[p][!u];
        }
        else p = son[p][u];
    }
    return ans;
}

class Solution {
public:
    vector maximizeXor(vector& nums, vector>& queries) {
        memset(son,0,sizeof son);
        idx = 0;
        sort(nums.begin(),nums.end());
        //离线思想,因此需要对queries加一个pos,因为回答是乱序的
        int pos = 0;
        for(auto& q: queries){
            q.push_back(pos++);
        }
        sort(queries.begin(),queries.end(),[](const auto& a,const auto& b){
            return a[1] < b[1];
        });
        vector ans(queries.size());
        int cur = 0;
        for(const auto& q : queries){
            int xi = q[0], mi = q[1],id = q[2];
            while(cur < nums.size() and nums[cur] <= mi){
                insert(nums[cur]);
                cur++;
            }
            if(cur == 0) ans[id] = -1;
            else ans[id] = query(xi);
        }
        return ans;
    }
};

   转载规则


《【Day27】1707.与数组中元素的最大异或值》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day28】664.奇怪的打印机 【Day28】664.奇怪的打印机
664. 奇怪的打印机有台奇怪的打印机有以下两个特殊要求: 打印机每次只能打印由 同一个字符 组成的序列。 每次可以在任意起始和结束位置打印新字符,并且会覆盖掉原来已有的字符。 给你一个字符串 s ,你的任务是计算这个打印机打印它需要的
2021-05-24
下一篇 
【Day26】810.黑板异或游戏 【Day26】810.黑板异或游戏
810. 黑板异或游戏黑板上写着一个非负整数数组 nums[i] 。Alice 和 Bob 轮流从黑板上擦掉一个数字,Alice 先手。如果擦除一个数字后,剩余的所有数字按位异或运算得出的结果等于 0 的话,当前玩家游戏失败。 (另外,如果
2021-05-22
  目录