建设彩票网站需要多少投资,找大学生做网站要多少钱,vs 手机网站开发,做外贸哪些网站好作者推荐
【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字
本文涉及知识点
动态规划汇总 状态压缩 记忆化搜索
1681. 最小不兼容性
给你一个整数数组 nums 和一个整数 k 。你需要将这个数组划分到 k 个相同大小的子集中#xff0c;使得同一…作者推荐
【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字
本文涉及知识点
动态规划汇总 状态压缩 记忆化搜索
1681. 最小不兼容性
给你一个整数数组 nums 和一个整数 k 。你需要将这个数组划分到 k 个相同大小的子集中使得同一个子集里面没有两个相同的元素。 一个子集的 不兼容性 是该子集里面最大值和最小值的差。 请你返回将数组分成 k 个子集后各子集 不兼容性 的 和 的 最小值 如果无法分成分成 k 个子集返回 -1 。 子集的定义是数组中一些数字的集合对数字顺序没有要求。 示例 1 输入nums [1,2,1,4], k 2 输出4 解释最优的分配是 [1,2] 和 [1,4] 。 不兼容性和为 (2-1) (4-1) 4 。 注意到 [1,1] 和 [2,4] 可以得到更小的和但是第一个集合有 2 个相同的元素所以不可行。 示例 2 输入nums [6,3,8,1,3,1,2,2], k 4 输出6 解释最优的子集分配为 [1,2][2,3][6,8] 和 [1,3] 。 不兼容性和为 (2-1) (3-2) (8-6) (3-1) 6 。 示例 3 输入nums [5,3,3,6,3,3], k 3 输出-1 解释没办法将这些数字分配到 3 个子集且满足每个子集里没有相同数字。 提示 1 k nums.length 16 nums.length 能被 k 整除。 1 nums[i] nums.length
动态规划
对nums按升序排序。
动态规划的状态表示
pre[mask][end] 记录最小不兼容性和。mask表示nums中那些元素已经选择选择的数优先放组号小的组。1组满了后才放2组2组满了才放三组 ⋯ \cdots ⋯
动态规划的转移方程
mask1 mask | (1 j ) end1 j j必须符合以下条件
j未被使用。如果是某个组的首元素可以选择任意元素。如果不是某个组的首元素j end。且nums[j] ! nums[end] { d p [ m a s k 1 ] [ j ] d p [ m a s k ] [ e n d ] 某组的首元素 d p [ m a s k 1 ] [ j ] d p [ m a s k ] [ e n d ] n u m s [ j ] − n u m s [ e n d ] 非组首元素 \begin{cases} dp[mask1][j] dp[mask][end] 某组的首元素\\ dp[mask1][j] dp[mask][end] nums[j]-nums[end] 非组首元素 \end{cases} {dp[mask1][j]dp[mask][end]dp[mask1][j]dp[mask][end]nums[j]−nums[end]某组的首元素非组首元素
动态规划的初始值
dp[0][0]全部为0其它全部为10000。
动态规划的填表顺序
mask从小到大枚举前置条件。
动态规划的返回值
dp.back()的最小值。
代码
核心代码
class Solution {
public:int minimumIncompatibility(vectorint nums, int k) {m_c nums.size();m_iMaskCount 1 m_c;sort(nums.begin(), nums.end());vectorint vBitCount(m_iMaskCount);for (int i 1; i m_iMaskCount; i){vBitCount[i] 1 vBitCount[i (i - 1)];}vectorvectorint dp(m_iMaskCount, vectorint(m_c, m_iNotMay));dp[0][0] 0;for (int mask 0; mask m_iMaskCount; mask){bool bGroupFirst (0 vBitCount[mask] % (m_c / k));for (int end 0; end m_c; end){for (int j bGroupFirst ? 0 : (end 1); j m_c; j){if ((1 j) mask){continue;//已经选择}if ((nums[j] nums[end]) (!bGroupFirst)){continue;//相同} const int iNew dp[mask][end] (bGroupFirst ? 0 : (nums[j]-nums[end]));dp[mask | (1 j)][j] min(dp[mask | (1 j)][j],iNew);}}}const int iRet *std::min_element(dp.back().begin(), dp.back().end());return (iRet m_iNotMay) ? -1 : iRet;}int m_c, m_iMaskCount,m_iNotMay10000;
};测试用例 templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){Assert(v1[i], v2[i]);}}int main()
{ vectorint nums;int k;{Solution sln;nums { 1 }, k 1;auto res sln.minimumIncompatibility(nums, k);Assert(res, 0);}{Solution sln;nums { 1,1 }, k 1;auto res sln.minimumIncompatibility(nums, k);Assert(res, -1);}{Solution sln;nums { 1, 2, 1, 4 }, k 2;auto res sln.minimumIncompatibility(nums, k);Assert(res, 4);}{Solution sln;nums { 6, 3, 8, 1, 3, 1, 2, 2 }, k 4;auto res sln.minimumIncompatibility(nums, k);Assert(res, 6);}{Solution sln;nums { 5,3,3,6,3,3 }, k 3;auto res sln.minimumIncompatibility(nums, k);Assert(res, -1);}{Solution sln;nums { 11,11,3,4,2,16,14,13,6,14,2,5,10,13,5,7 }, k 8;auto res sln.minimumIncompatibility(nums, k);Assert(res, 12);}
}记忆化搜索动态规划
从后置条件倒推前置条件可以省去大量不必要的状态。运行速度提高500%。缺点可理解性大幅降低。 mask 选择了那些数end 是最一个数。如果本组只有一个数则最小不兼容性和就是 除本数外 的前几个完整的组的最小不兼容性和。 如果完整的组最后一个元素一定是最大值。最大值一定是某个组的最后一个。将此组调到最后一组结果不变。 EndZeroCount 从右到左为1的第一个下标从0开始。为了一致nums降序排序。 每组一个元素要特殊处理。
int EndZeroCount(unsigned x )
{for (int i 0; i 32; i){if ((1 i) x){return i;}}return 32;
}class Solution {
public:int minimumIncompatibility(vectorint nums, int k) {m_c nums.size();m_iMaskCount 1 m_c;m_pre m_c / k;if (1 m_pre){return 0;} sort(nums.begin(), nums.end(),std::greater());m_nums nums;m_vBitCount.resize(m_iMaskCount);for (int i 1; i m_iMaskCount; i){m_vBitCount[i] 1 m_vBitCount[i (i - 1)];}m_dp.assign(m_iMaskCount, vectorint(m_c, m_iNotMay));const int iRet Rec(m_iMaskCount-1);return (iRet m_iNotMay) ? -1 : iRet;}int Rec(int mask, int end){if (0 mask){return 0;}auto res m_dp[mask][end];if (m_iNotMay ! res){return res;}const int iPreMask mask ^ (1 end);const int cnt m_vBitCount[mask] % m_pre;//最后一组数量if (1 cnt ){return res Rec(iPreMask);}for (int i end1 ; i m_c; i){if ((1 i) mask){if (m_nums[i] ! m_nums[end]){res min(res, Rec(iPreMask,i) m_nums[end]-m_nums[i]);}}}return res;}int Rec(int mask){return Rec(mask, EndZeroCount(mask));}int m_c, m_iMaskCount,m_iNotMay10000, m_pre;vectorint m_vBitCount;vectorvectorint m_dp;vectorint m_nums;
};2023年2月版
class Solution { public: int minimumIncompatibility(vector nums, int k) { m_c nums.size(); if (k m_c) { return 0; } if (1 k) { std::set setNums(nums.begin(), nums.end()); if (nums.size() ! setNums.size()) { return -1; } return *setNums.rbegin() - *setNums.begin(); } std::sort(nums.begin(),nums.end()); m_iMaskNum (1 m_c )*m_c; m_vMaskByBits.resize(m_c 1); m_vMaskByBits[0].push_back(0); vector vMaskBits(m_iMaskNum); for (int mask 1; mask m_iMaskNum; mask) { const int iSelMask mask / m_c; vMaskBits[mask] vMaskBits[(iSelMask(iSelMask - 1))m_c] 1; m_vMaskByBits[vMaskBits[mask]].push_back(mask); } m_vMaskGroupFirstToMin.resize(m_iMaskNum, m_iNotMay); m_vMaskGroupFirstToMin[0] 0; for (int i 0; i nums.size(); i) { vector dp(m_iMaskNum, m_iNotMay); for (int iMask : m_vMaskByBits[i]) { if (m_iNotMay m_vMaskGroupFirstToMin[iMask]) { continue; } const int iSelMask iMask / m_c; const int iPreSel iMask% m_c; if (0 i % (m_c/k)) {//新组 for (int j 0; j m_c; j) { if (iSelMask (1 j)) { continue; } const int iNewMask JoinMask(iSelMask | (1 j), j); dp[iNewMask] min(dp[iNewMask], min(m_vMaskGroupFirstToMin[iMask],dp[iMask])); } } else { for (int j iPreSel1; j m_c; j) { if (iSelMask (1 j)) { continue; } const int iAdd nums[j] - nums[iPreSel]; if (0 iAdd) { continue; } const int iNewMask JoinMask(iSelMask | (1 j), j); dp[iNewMask] min(dp[iNewMask], min(m_vMaskGroupFirstToMin[iMask], dp[iMask]) iAdd); } } } m_vMaskGroupFirstToMin.swap(dp); } std::set setRet; for (int iPre 0; iPre m_c; iPre) { int iIndex (1 m_c) - 1; iIndex iIndexm_c iPre; setRet.insert(m_vMaskGroupFirstToMin[iIndex]); } int iMin setRet.begin(); return (m_iNotMay iMin) ? -1 : iMin; } int JoinMask(int iSelMask, int iNewSelIndex) { return iSelMaskm_c iNewSelIndex; } vector m_vMaskGroupFirstToMin; int m_c; int m_iMaskNum; vectorvector m_vMaskByBits; const int m_iNotMay 1000 * 1000; };
2023年9月版
class Solution { public: int minimumIncompatibility(vector nums, int k) { m_c nums.size(); if (k m_c) { return 0; } m_iMaskNum 1 m_c; if (0 ! m_c % k) { return -1; } const int iNumOfAGroup m_c / k; vectorvector vBitMask(m_c1); vBitMask[0].emplace_back(0); for (int mask 1; mask m_iMaskNum; mask) { vBitMask[bitcount((unsigned int)mask)].emplace_back(mask); } std::unordered_mapint, int mMaskCom; for (int mask : vBitMask[iNumOfAGroup]) { int iMax INT_MIN, iMin INT_MAX; unordered_set setValues; for (int j 0; j m_c; j) { if (mask (1 j)) { MaxSelf(iMax, nums[j]); MinSelf(iMin, nums[j]); setValues.emplace(nums[j]); } } if (setValues.size() ! iNumOfAGroup) { continue; } mMaskCom[mask] iMax - iMin; } int pre[1 16] { 0 }; for (const auto it : mMaskCom) { pre[it.first] it.second; } for (int i 2; i k; i) { int dp[1 16] { 0 }; for (const int mask : vBitMask[iNumOfAGroup*i]) { for (int sub mask; sub; sub (sub - 1) mask) { if ((0 ! pre[sub]) mMaskCom.count(mask - sub)) { int iNew pre[sub] mMaskCom[mask - sub]; if (0 ! dp[mask]) { iNew min(iNew, dp[mask]); } dp[mask] iNew; } } } memcpy(pre, dp, sizeof(dp)); } return pre[m_iMaskNum - 1] ? pre[m_iMaskNum - 1] : -1; } int m_c, m_iMaskNum; };
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
