【动态规划】【位运算】1787. 使所有区间的异或结果为零

作者推荐

【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字

本文涉及知识点

动态规划汇总
位运算

LeetCode 1787. 使所有区间的异或结果为零

给你一个整数数组 nums​​​ 和一个整数 k​​​​​ 。区间 [left, right]（left <= right）的 异或结果 是对下标位于 left 和 right（包括 left 和 right ）之间所有元素进行 XOR 运算的结果：nums[left] XOR nums[left+1] XOR … XOR nums[right] 。
返回数组中 要更改的最小元素数 ，以使所有长度为 k 的区间异或结果等于零。
示例 1：
输入：nums = [1,2,0,3,0], k = 1
输出：3
解释：将数组 [1,2,0,3,0] 修改为 [0,0,0,0,0]
示例 2：
输入：nums = [3,4,5,2,1,7,3,4,7], k = 3
输出：3
解释：将数组 [3,4,5,2,1,7,3,4,7] 修改为 [3,4,7,3,4,7,3,4,7]
示例 3：
输入：nums = [1,2,4,1,2,5,1,2,6], k = 3
输出：3
解释：将数组[1,2,4,1,2,5,1,2,6] 修改为 [1,2,3,1,2,3,1,2,3]
提示：
1 <= k <= nums.length <= 2000
​​​​​​0 <= nums[i] < 2¹⁰

动态规划

异或

异或$\oplus$的逆运算是其本身。所以nums[i]和nums[i+k] 都等于0和nums(i,i+k)的$\oplus$。

动态规划的状态表示

pre[mask] 表示nums[0,i)的结果为mask最小更改次数。修nums[j]，必须同时修改nums[j+k]…nums[j*+k*x]
dp[mask]表示nums[0,i+1)的结果为mask最小更改次数。
由于nums[i] 中只有0到9位有1，所有不需要处理第10位及更高位。
mask的取值范围2¹⁰，空间复杂度为:*O(2¹⁰)

动态规划的转移方程

mCnt 记录nums[i] ,nums[i+k] nums[i+k * 2]…nums[i+k * 3]… 各数值出现的次数。所有数值出现的次数之和为cnt。
令x在mCnt中出现。
dp[mask] =min { p r e [ m a s k ⊕ x ] + c n t − m C n t [ x ] 部分数字没改 情况一 ‾ 除 p r e [ m a s k ⊕ x ] 外的最小值 + c n t 改成数字 情况二 ‾

$$\begin{cases} pre[mask \oplus x]+cnt-mCnt[x] & 部分数字没改& \underline{情况一} \\ 除 pre[mask \oplus x]外的最小值+cnt & 改成数字& \underline{情况二} \\ \end{cases}$$ {pre[mask⊕x]+cnt−mCnt[x]除pre[mask⊕x]外的最小值+cnt​部分数字没改改成数字​情况一​情况二​​
情况二，可以不排除$mask\oplus x$ ，假定它是最小值，它一定被情况一淘汰，比情况一多mCnt[x]。
故：每个状态的转移的时间复杂度是:O(1)。

动态规划的初始状态

pre[0]=0 其它等于10000，表示非法状态。

动态规划的填表顺序

i从0到k-1。枚举nums，时间复杂度O(n)。状态数，O(2¹⁰)。古总时间复杂度：O(n2¹⁰)。

动态规划的返回值

pre.front();

代码

核心代码

class Solution {
public:
	int minChanges(vector<int>& nums, int k) {
		int n = nums.size();
		vector<int> pre(m_iMaskCount, 10000);
		pre[0] = 0;
		for (int i = 0; i < k; i++)
		{
			int cnt = 0,j;
			unordered_map<int, int> mCnt;
			for (; (j= cnt*k+i) < n; cnt++)
			{
				mCnt[nums[j]]++;
			}
			vector<int> dp(m_iMaskCount, 10000);
			int iMinPre = *std::min_element(pre.begin(), pre.end());
			for (int mask = 0; mask < m_iMaskCount; mask++)
			{
				dp[mask] = iMinPre + cnt;
				for (const auto& [x, cnt1] : mCnt)
				{
					dp[mask] = min(dp[mask], pre[mask ^ x] + cnt - cnt1);
				}
			}
			pre.swap(dp);
		}
		return pre.front();
	}
	int m_iMaskCount = 1 << 10;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{	
	vector<int> nums;
	int k;
	{
		Solution sln;
		nums = { 1, 2, 0, 3, 0 }, k = 1;
		auto res = sln.minChanges(nums, k);
		Assert(res, 3);
	}
	
	{
		Solution sln;
		nums = { 3,4,5,2,1,7,3,4,7 }, k = 3;
		auto res = sln.minChanges(nums, k);
		Assert(res, 3);
	}

	{
		Solution sln;
		nums = { 1,2,4,1,2,5,1,2,6 }, k = 3;
		auto res = sln.minChanges(nums, k);
		Assert(res, 3);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

2023年2月

class Solution {
public:
int minChanges(vector& nums, int k) {
vector pre(1024, m_iNotMay);
pre[0] = 0;
for (int i = 0; i < k; i++ )
{
const auto& n = nums[i];
int iSize = 0;
std::unordered_map<int, int> mValueNums;
for (int ii = i; ii < nums.size(); ii+=k)
{
iSize++;
mValueNums[nums[ii]]++;
}
int t2min = *std::min_element(pre.begin(), pre.end());
vector dp(1024, t2min);
for (int mask = 0; mask < 1024; mask++)
{
for (auto it : mValueNums)
{
dp[mask] = min(dp[mask], pre[mask^it.first] - it.second);
}
}
for (auto& na : dp)
{
na += iSize;
}
pre.swap(dp);
}
return pre[0];
}
int m_iNotMay = 1000 * 1000;
};

2023年7月

class Solution {
public:
int minChanges(vector& nums, int k) {
m_c = nums.size();
vector pre(m_iMaskNum, m_iNotMay);
pre[0] = 0;
for (int iK = 0; iK < k; iK++)
{
std::unordered_map<int, int> count;
int iGroupNumNum = 0;
for (int i = iK; i < m_c; i += k)
{
count[nums[i]]++;
iGroupNumNum++;
}
const int iMinPre = *std::min_element(pre.begin(), pre.end());
vector dp(m_iMaskNum, iMinPre + iGroupNumNum);
for (const auto& it : count)
{
for (int iPre = 0; iPre < m_iMaskNum; iPre++)
{
const int iNewMask = it.first ^ iPre;
dp[iNewMask] = min(dp[iNewMask],pre[iPre]+ iGroupNumNum - it.second);
}
}
pre.swap(dp);
}
return pre[0];
}
int m_iMaskNum = 1 << 10;
const int m_iNotMay = 10000;
int m_c;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。