目录
题目
给你一个整数数组 nums 和一个整数 k 。区间 [left, right](left <= right)的 异或结果 是对下标位于 left 和 right(包括 left 和 right )之间所有元素进行 XOR 运算的结果:nums[left] XOR nums[left+1] XOR … XOR nums[right] 。
返回数组中 要更改的最小元素数 ,以使所有长度为 k 的区间异或结果等于零。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/make-the-xor-of-all-segments-equal-to-zero
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
提示:
1 <= k <= nums.length <= 2000
0 <= nums[i] < 210
思路
一开始我这么想的
举个例子,k=3,那么n[1]^n[2]^n[3] = 0,n[2]^n[3]^n[4] = 0。所以,n[1]=n[4],即n[i]=n[i+k]
假设以k为一组,统计k中每一位数组出现的个数,个数最多的不变。(大坑,我没有考虑如果n[1]^n[2]^n[3] != 0怎么办)
答案(错误)
class Solution {
public:
int minChanges(vector<int>& nums, int k) {
map<int,int> num_count;//存储key出现的value次
vector<int> knums;//存储出现的最大值
int XOR; //存储异或值
int len = nums.size();//数组长度
int circle = int(len/k);//有几轮重复的
int res = len%k;//剩余的
for(int i=0;i<k;i++){
for(int j=0;j<=circle;j++){
int index = j*k+i; //nums的下标
if(index >= len) continue;
num_count[nums[index]]++;
}
vector<int> temp;
map<int, int>::iterator iter;
int max = 0;
int flag = 0;
for(iter = num_count.begin(); iter != num_count.end(); iter++){
if(iter->second>max) {
flag = iter->first;
max = iter->second;
}
}
knums.push_back(max) ;
XOR = XOR^flag;
num_count.clear();
}
int r = 0;
for(int i=0;i<k;i++){
if(XOR==0){
r = r+ (circle - knums[i]);
}else{
//这里卡住了。如果异或不为0的话,还要考虑每个circle中有几个满足异或为0的。
//我发现不能不用算法来做了。
//大失败,开始就没考虑清楚题,以至于花了很久在调错上面,下次还是要考虑清楚。
//去看算法吧
}
}
if(res==0){
return r;
}else{
return r+res;
}
}
};
修改
看了题解还是脱不开动态规划。没时间仔细复盘了,有空写。
class Solution {
private:
// x 的范围为 [0, 2^10)
static constexpr int MAXX = 1 << 10;
// 极大值,为了防止整数溢出选择 INT_MAX / 2
static constexpr int INFTY = INT_MAX / 2;
public:
int minChanges(vector<int>& nums, int k) {
int n = nums.size();
vector<int> f(MAXX, INFTY);
// 边界条件 f(-1,0)=0
f[0] = 0;
for (int i = 0; i < k; ++i) {
// 第 i 个组的哈希映射
unordered_map<int, int> cnt;
int size = 0;
for (int j = i; j < n; j += k) {
++cnt[nums[j]];
++size;
}
// 求出 t2
int t2min = *min_element(f.begin(), f.end());
vector<int> g(MAXX, t2min);
for (int mask = 0; mask < MAXX; ++mask) {
// t1 则需要枚举 x 才能求出
for (auto [x, countx]: cnt) {
g[mask] = min(g[mask], f[mask ^ x] - countx);
}
}
// 别忘了加上 size
for_each(g.begin(), g.end(), [&](int& val) {val += size;});
f = move(g);
}
return f[0];
}
};
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/make-the-xor-of-all-segments-equal-to-zero/solution/shi-suo-you-qu-jian-de-yi-huo-jie-guo-we-uds2/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
时间复杂度:O( 2C k + n),其中 n 是数组 nums 的长度,C 是数组 nums 中元素二进制表示的最大位数,在本题中 C = 10。对于每一个组,构造其哈希表的时间严格小于动态规划的时间,因此可以忽略不计。
空间复杂度:O(2C + n/k)动态规划需要两个长度为 2C的一维数组,每一个组 i对应的哈希表的大小为 O(n/k)