[LeetCode] 1310. XOR Queries of a Subarray 子数组异或查询
2022/7/8 23:55:30
本文主要是介绍[LeetCode] 1310. XOR Queries of a Subarray 子数组异或查询,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
You are given an array arr
of positive integers. You are also given the array queries
where queries[i] = [lefti, righti]
.
For each query i
compute the XOR of elements from lefti
to righti
(that is, arr[lefti] XOR arr[lefti + 1] XOR ... XOR arr[righti]
).
Return an array answer
where answer[i]
is the answer to the ith
query.
Example 1:
Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]] Output: [2,7,14,8] Explanation: The binary representation of the elements in the array are: 1 = 0001 3 = 0011 4 = 0100 8 = 1000 The XOR values for queries are: [0,1] = 1 xor 3 = 2 [1,2] = 3 xor 4 = 7 [0,3] = 1 xor 3 xor 4 xor 8 = 14 [3,3] = 8
Example 2:
Input: arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]] Output: [8,0,4,4]
Constraints:
1 <= arr.length, queries.length <= 3 * 104
1 <= arr[i] <= 109
queries[i].length == 2
0 <= lefti <= righti < arr.length
这道题给了一个正整数数组,和一堆查询区间,让计算每个区间内所有的数字的'异或'和。博主看到这种玩区间的题目,首先想到的是建立累加和数组,但是这里不是求区间和,而是区间内数字的'异或'和,所以需要研究一下这种这种思路是否在这里同样适用。这里的'异或'是位操作,简单来说就是相同取0,不同取1,根据这个性质可以得出两个结论,第一个结论是相同的数字'异或'后为0,因为相同的数字每一位都是相同的,'异或'后均为0。第二个结论是任何数字'异或'0之后均为其本身不变,因为0'异或'0还是0,0'异或'1后仍为1,并不发生任何变化。
理解了这两条性质后,再来研究下区间,若原数组为 [a, b, c, d],若想求 c^d
,可不可以通过整个区间的'异或'和 a^b^c^d
,和前两个数字的'异或' a^b
来得到呢,其实是可以的,将二者'异或'起来,变成 a^b^c^d^a^b
,调整下顺序,变为 a^a^b^b^c^d
,根据之前分析的性质可以得到 c^d
。所以这道题还是可以使用累加和数组的思路来做,只不过这里变成了累加'异或'和数组。分析道这里,应该就不难写出代码了,首先建立累加'异或'和数组,这里长度为 n+1,方便处理边界,对于每个给定区间 [i, j] 的'异或'和计算方法,就是用 xors[j+1]^xors[i]
即可,参见代码如下:
class Solution { public: vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) { int n = arr.size(); vector<int> res, xors(n + 1); for (int i = 1; i <= n; ++i) { xors[i] = xors[i - 1] ^ arr[i - 1]; } for (auto &query : queries) { res.push_back(xors[query[1] + 1] ^ xors[query[0]]); } return res; } };
Github 同步地址:
https://github.com/grandyang/leetcode/issues/1310
参考资料:
https://leetcode.com/problems/xor-queries-of-a-subarray/
https://leetcode.com/problems/xor-queries-of-a-subarray/discuss/470702/C%2B%2B-Prefix-XORs
https://leetcode.com/problems/xor-queries-of-a-subarray/discuss/470787/JavaC%2B%2BPython-Straight-Forward-Solution
LeetCode All in One 题目讲解汇总(持续更新中...)
这篇关于[LeetCode] 1310. XOR Queries of a Subarray 子数组异或查询的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升