作者推荐
【数位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] < 210
动态规划
异或
异或⊕ \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*2+k]
dp[mask]表示nums[0,i+1)的结果为mask最小更改次数。
由于nums[i] 中只有0到9位有1，所有不需要处理第10位及更高位。
mask的取值范围210，空间复杂度为:*O(210)
动态规划的转移方程
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部分数字没改改成数字情况一情况二
情况二，可以不排除m a s k ⊕ x mask \oplus xmask⊕x ，假定它是最小值，它一定被情况一淘汰，比情况一多mCnt[x]。
故：每个状态的转移的时间复杂度是:O(1)。
动态规划的初始状态
pre[0]=0 其它等于10000，表示非法状态。
动态规划的填表顺序
i从0到k-1。枚举nums，时间复杂度O(n)。状态数，O(210)。古总时间复杂度：O(n210)。
动态规划的返回值
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; };
测试用例
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); } }
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;
};
