📍前言
🕺作者: 迷茫的启明星
学习路线
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多平台发布