【前缀和】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
|
4月前
|
存储
2559. 统计范围内的元音字符串数(前缀和) o(n)时间复杂度
2559. 统计范围内的元音字符串数(前缀和) o(n)时间复杂度
|
6月前
|
机器学习/深度学习 算法 测试技术
【排序 贪心】3107. 使数组中位数等于 K 的最少操作数
【排序 贪心】3107. 使数组中位数等于 K 的最少操作数
【排序 贪心】3107. 使数组中位数等于 K 的最少操作数
|
6月前
力扣421. 数组中两个数的最大异或值(字典树)
力扣421. 数组中两个数的最大异或值(字典树)
|
6月前
|
索引
Leetcode 给定一个数组,给定一个数字。返回数组中可以相加得到指定数字的两个索引
Leetcode 给定一个数组,给定一个数字。返回数组中可以相加得到指定数字的两个索引
|
6月前
|
算法 前端开发
二的幂数组中查询范围内的乘积
二的幂数组中查询范围内的乘积
37 0
|
6月前
【每日一题Day142】LC1590使数组和能被 P 整除 | 前缀和+哈希表
【每日一题Day142】LC1590使数组和能被 P 整除 | 前缀和+哈希表
41 0
|
机器学习/深度学习 算法
268. 丢失的数字 :「排序」&「计数」&「原地哈希」&「数学」&「异或」
268. 丢失的数字 :「排序」&「计数」&「原地哈希」&「数学」&「异或」
|
存储 算法 C语言
【前缀和】1310.子数组异或查询
本篇将学习前缀和OJ题子数组异或查询相关知识。
92 0
判断一个数是否是对称数(数组/非数组解法)
判断一个数是否是对称数(数组/非数组解法)