leetcode每日一题
[1738] 找出第 K 大的异或坐标值
[1744] 你能在你最喜欢的那天吃到你最喜欢的糖果吗?
[231] 2的幂
堆排复习
[461] 汉明距离
[1190] 反转每对括号间的子串
[1707] 与数组中元素的最大异或值
[810] 黑板异或游戏
[1035] 不相交的线
[692] 前K个高频单词
[872] 叶子相似的树
[1442] 形成两个异或相等数组的三元组数目
[993] 二叉树的堂兄弟节点
[421] 数组中两个数的最大异或值
[13] 罗马数字转整数
[12] 整数转罗马数字
[1269]. 停在原地的方案数
[1310] 子数组异或查询
[1734] 解码异或后的排列
本文档使用 MrDoc 发布
-
+
首页
[1310] 子数组异或查询
[1310] 子数组异或查询 [https://leetcode-cn.com/problems/xor-queries-of-a-subarray/](https://leetcode-cn.com/problems/xor-queries-of-a-subarray/) 有一个正整数数组 arr,现给你一个对应的查询数组 queries,其中 queries[i] = [Li, Ri]。 对于每个查询 i,请你计算从 Li 到 Ri 的 XOR 值(即 arr[Li] xor arr[Li+1] xor ... xor arr[Ri])作为本次查询的结果。 并返回一个包含给定查询 queries 所有结果的数组。 示例 1: ``` 输入:arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]] 输出:[2,7,14,8] 解释: 数组中元素的二进制表示形式是: 1 = 0001 3 = 0011 4 = 0100 8 = 1000 查询的 XOR 值为: [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 ``` 示例 2: ``` 输入:arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]] 输出:[8,0,4,4] ``` 题解: ``` 由题知 该疑惑区间是连续的,而由异或性质可知:a[2]^a[3]^a[4] = a[1]^a[2]^a[2]^a[4] ^ a[1] 即 [Li,Ri]的异或值为 a[Li] ^ a[Li + 1] ^...^a[Ri] = (a[0] ^ a[1] ^ .. ^ a[Ri]) ^ (a[0] ^ a[1] ^ .. ^ a[Li - 1]) 即可先求出前n个数的异或值以减少时间复杂度。 ``` 代码如下: ```cpp class Solution { public: vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) { std::vector<int> tmp_resurt; //用来保存从0到n异或的值 int start_num = 0; for(int i = 0; i < (int)arr.size(); ++i) { start_num ^= arr[i]; tmp_resurt.push_back(start_num); } std::vector<int> resurt; for(int i = 0; i < (int)queries.size(); ++i) { if((int)queries[i].size() < 2) return resurt; //越界保护 int begin_num = queries[i][0] - 1; int end_num = queries[i][1]; int xor_begin_num = 0; //初值为0的目的:0与任何值异或都为该值本身 if (begin_num >= 0 && begin_num < (int)tmp_resurt.size()) //越界保护 { xor_begin_num = tmp_resurt[begin_num]; } int xor_end_num = 0; if (end_num >= 0 && end_num < (int)tmp_resurt.size()) //越界保护 { xor_end_num = tmp_resurt[end_num]; } int num = xor_begin_num ^ xor_end_num; resurt.push_back(num); } return resurt; } }; ```
ty
2021年5月12日 10:47
转发文档
收藏文档
上一篇
下一篇
手机扫码
复制链接
手机扫一扫转发分享
复制链接
阅读量
次
本站总访问量
次
本站访客数
人次
Markdown文件
分享
链接
类型
密码
更新密码