5304. 子数组异或查询
分析:
方法 1: 暴力求解: 每次循环, 从到 Li 到 Ri 的异或和, 存入 vector 并返回; 这种方法无疑会超时;
- class Solution {
- public:
- vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
- vector<int> res;
- vector<vector<int>> dp;
- vector<int> level;
- int len=arr.size();
- int count;
- // 循环找
- for(int i=0;i<queries.size();i++)
- {
- count=0;
- int x = queries[i][0]>queries[i][1]?queries[i][1]:queries[i][0];
- int y = queries[i][0]>queries[i][1]?queries[i][0]:queries[i][1];
- for(int i=x;i<=y;i++)
- {
- count^=arr[i];
- }
- res.push_back(count);
- }
- return res;
- }
- };
方法 2: 二维数组: dp[i][j] 表示从 i 到 j 的异或和, dp[i][j]=dp[i][j-1] ^ arr[j]; 当数字的个数为 n 时, 需要开辟 n*n 的空间, 并且浪费掉了 1/2 的空间, 因为 dp[i][j]=dp[j][i];
- class Solution {
- public:
- vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
- vector<int> res;
- vector<vector<int>> dp;
- int len=arr.size();
- dp.resize(len,arr); // 初始化
- for(int i=0;i<len;i++)
- {
- for(int j=i;j<len;j++)
- {
- // 填充 dp 数组 dp[i][j] 表示从 i 到 j 异或的结果
- if(i==j)
- dp[i][j]=arr[i];
- else
- dp[i][j]=dp[i][j-1]^arr[j];
- }
- }
- // 循环找
- for(int i=0;i<queries.size();i++)
- {
- //int x = queries[i][0]>queries[i][1]?queries[i][1]:queries[i][0];
- //int y = queries[i][0]>queries[i][1]?queries[i][0]:queries[i][1];
- res.push_back(dp[queries[i][0]]queries[i][1]]);
- }
- return res;
- }
- };
方法 3: 在方法 2 的基础上, 砍掉一半空间, 但是结果还是超出了空间的最大消耗;
- class Solution {
- public:
- vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
- vector<int> res;
- vector<vector<int>> dp;
- vector<int> level;
- int len=arr.size();
- for(int i=0;i<len;i++)
- {
- level.resize(len-i,0);
- for(int j=0;j<len-i;j++)
- {
- // 填充 dp 数组 dp[i][j] 表示从 i 到 j 异或的结果
- if(j==0)
- level[j]=arr[j+i];
- else
- level[j]=level[j-1]^arr[j+i];
- }
- dp.push_back(level);
- }
- // 循环找
- for(int i=0;i<queries.size();i++)
- {
- int x = queries[i][0]>queries[i][1]?queries[i][1]:queries[i][0];
- int y = queries[i][0]>queries[i][1]?queries[i][0]:queries[i][1];
- res.push_back(dp[x][y-x]);
- }
- return res;
- }
- };
方法 4: 看了题解, 才知道还能这么算, 直接保留前 Ri 项的异或和, 然后再和前 Li 项的异或和做异或操作, 相同的前 Li 项就被抵消掉了, 空间消耗直接变成了 n.
- class Solution {
- public:
- vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
- vector<int> dp;
- dp.resize(arr.size(),0);
- dp[0]=arr[0];
- for(int i=1;i<arr.size();i++)
- {
- dp[i]=dp[i-1]^arr[i];
- }
- vector<int> res;
- for(int i=0;i<queries.size();i++)
- {
- int l=queries[i][0];
- int r=queries[i][1];
- int num=(l==0)?dp[r]:(dp[r]^dp[l-1]);
- res.push_back(num);
- }
- return res;
- }
- };
来源: http://www.bubuko.com/infodetail-3366799.html