【前缀和】1829. 每个查询的最大异或值

简介: 【前缀和】1829. 每个查询的最大异或值

📍前言

🕺作者: 迷茫的启明星


学习路线

C语言从0到1

C++初阶

数据结构从0到1

😘欢迎关注:👍点赞🙌收藏✍️留言


🏇码字不易,你的👍点赞🙌收藏❤️关注对我真的很重要,有问题可在评论区提出,感谢阅读!!!


持续更新中~


【前缀和】1829. 每个查询的最大异或值

问题描述

给定一个有序数组 nums,它由 n 个非负整数组成,同时给定一个整数 maximumBit。你需要执行以下查询 n 次:


找到一个非负整数 k,满足 k < 2^maximumBit,使得 nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k 的结果最大化。k 是第 i 个查询的答案。


从当前数组 nums 删除最后一个元素。


请返回一个数组 answer,其中 answer[i] 是第 i 个查询的结果。


解题方法

我们可以通过前缀和与位运算的方法来解决这个问题。以下是解题步骤:


计算前缀异或和

首先,我们需要计算数组 nums 的前缀异或和。这可以通过 std::accumulate 函数实现。我们将结果存储在变量 xorsum 中。


int xorsum = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());


int xorsum =: 定义一个名为xorsum的整数变量,用于存储计算得到的异或和。


accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());: 这是一个调用std::accumulate函数的代码。accumulate是C++标准库中的一个算法,用于对序列执行某些操作,并将结果累积到初始值。


nums.begin()和nums.end(): 这是序列nums的开始和结束迭代器。nums是一个整数序列,可能表示一个数组或向量。


0: 这是累积的初始值。在计算异或和的情况下,我们使用0作为初始值,因为异或操作的性质允许我们将所有元素与0进行异或,从而得到序列中所有元素的异或和。


bit_xor<int>(): 这是一个函数对象,用于定义在序列上执行的操作。bit_xor是一个二元操作符,表示按位异或。在这里,我们使用bit_xor<int>()来对序列中的每个整数执行按位异或操作。


倒序遍历数组并计算答案

接下来,我们需要倒序遍历数组 nums,并计算每个查询的答案。我们使用一个 ans 数组来存储每个查询的答案。


vector<int> ans;
for (int i = n - 1; i >= 0; --i) {
    ans.push_back(xorsum ^ mask);
    xorsum ^= nums[i];
}



这里,我们首先将当前前缀异或和 xorsum 与 mask 进行异或操作,并将结果存入答案数组 ans。然后,我们将当前元素 nums[i] 从前缀异或和中删除,即将 xorsum 与 nums[i] 进行异或操作。


位运算优化

在这个问题中,我们需要找到一个非负整数 k,使得 nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k 的结果最大化。我们可以通过位运算来优化这个过程。


我们可以观察到,我们需要找到的整数 k 满足 k < 2^maximumBit。因此,我们可以使用一个 mask 变量来表示这个上限。我们可以将 mask 设置为 2^maximumBit - 1。


int mask = (1 << maximumBit) - 1;


通过使用 mask,我们可以将问题简化为找到 nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] 的最大子集,使得这些元素的异或和的结果在 mask 的范围内。


代码

class Solution {
public:
    vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
        int n = nums.size();
        int mask = (1 << maximumBit) - 1;
        int xorsum = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
        vector<int> ans;
        for (int i = n - 1; i >= 0; --i) {
            ans.push_back(xorsum ^ mask);
            xorsum ^= nums[i];
        }
        return ans;
    }
};


总结

通过前缀和与位运算的方法,我们可以高效地解决这道题目。我们首先计算前缀异或和,然后倒序遍历数组,计算每个查询的答案。通过使用位运算,我们可以简化问题并提高算法的效率。


本文由mdnice多平台发布


相关文章
|
6月前
|
算法 前端开发
找出前缀异或的原始数组
找出前缀异或的原始数组
36 0
|
6月前
力扣421. 数组中两个数的最大异或值(字典树)
力扣421. 数组中两个数的最大异或值(字典树)
|
6月前
|
索引
Leetcode 给定一个数组,给定一个数字。返回数组中可以相加得到指定数字的两个索引
Leetcode 给定一个数组,给定一个数字。返回数组中可以相加得到指定数字的两个索引
|
6月前
每日一题(づ ̄3 ̄)づ╭❤~(数字在升序数组中出现的次数,整数转换)
每日一题(づ ̄3 ̄)づ╭❤~(数字在升序数组中出现的次数,整数转换)
36 0
|
6月前
|
算法 前端开发
二的幂数组中查询范围内的乘积
二的幂数组中查询范围内的乘积
35 0
|
11月前
|
算法 测试技术 C#
C++字典树算法:找出强数对的最大异或值 II
C++字典树算法:找出强数对的最大异或值 II
|
存储 算法 C语言
【前缀和】1310.子数组异或查询
本篇将学习前缀和OJ题子数组异或查询相关知识。
90 0
|
编译器 API C语言
力扣面试题17.04 - 消失的数字【求和相减 + 异或位运算 + 哈希表】
三种方法巧解力扣面试题17.04 - 消失的数字,你值得拥有
144 0
力扣面试题17.04 - 消失的数字【求和相减 + 异或位运算 + 哈希表】
|
算法
算法练习——(1)找数组中唯一成对的那个数(异或)
——如何找数组中唯一成对的那个数(数组特殊) 1-1000这一千个数放在含有1001个元素的数组中,只有唯一的一个元素值重复,其他均只出现一次。 每个数组元素只能访问一次,设计一个算法,将他找出来;不用辅助储存空间,设计一个算法实现.
112 0
|
机器学习/深度学习 Python
字符串和数字的去重操作和鞍点的寻找
字符串和数字的去重操作和鞍点的寻找
字符串和数字的去重操作和鞍点的寻找