【状态压缩】【动态规划】【C++算法】691贴纸拼词

2024-01-19 16:52
文章标签 算法 动态 规划 c++ 压缩 状态 贴纸 拼词 691

本文主要是介绍【状态压缩】【动态规划】【C++算法】691贴纸拼词，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者推荐

【动态规划】【数学】【C++算法】18赛车

本文涉及知识点

状态压缩 动态规划

LeetCode:691 贴纸拼词

我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。
返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。
注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。
示例 1：
输入： stickers = [“with”,“example”,“science”], target = “thehat”
输出：3
解释：
我们可以使用 2 个 “with” 贴纸，和 1 个 “example” 贴纸。
把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。
此外，这是形成目标字符串所需的最小贴纸数量。
示例 2:
输入：stickers = [“notice”,“possible”], target = “basicbasic”
输出：-1
解释：我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。

提示:
n == stickers.length
1 <= n <= 50
1 <= stickers[i].length <= 10
1 <= target.length <= 15
stickers[i] 和 target 由小写英文单词组成

封装类

假定target串有个n1字符，数量分别为m_vMax[0] m_vMax[1]…m_vMax[n1-1]。
对于某个stickers串，忽略target中没有的字符。target第0 1 2… 个字符在sticker的数量为vNum[0],vNum[1]…
则第0个字符的mask为1*vNum[0]
第1个字符的mask为(m_vMax[0]+1)*vNum[1]
…
第i个字符的mask为：Mul [ 0 , i − 1 ] j \Large^j_{[0,i-1]} [0,i−1]j​(vMax[j]+1)*vNum[i]
总mask 为各字符mask之和。
注意： 无论如何vNum[i]都大于等于0，小于等于m_vMax[i]

class CMask
{
public:void Add(int iMax)//当前最高位范围[0,iMax]{m_vMax.emplace_back(iMax);m_iMaskCount *= (iMax + 1);}vector<int> FromMask(int iMask){vector<int> vNums;for (int i = 0; i < m_vMax.size(); i++){vNums.emplace_back(iMask % (m_vMax[i] + 1));iMask /= (m_vMax[i] + 1);}return vNums;}int ToMask(const vector<int>& vNums,int iMul=1){int iMask = 0;int iUnit = 1;for (int i = 0; i < m_vMax.size(); i++){iMask += iUnit * min(m_vMax[i],vNums[i]* iMul);iUnit *= (m_vMax[i]+1);}return iMask;}int MaskSubVector(int iMask, const vector<int>& vNums, const int iMul = 1){int iNewMask = 0;int iUnit = 1;for (int i = 0; i < m_vMax.size(); i++){int cur = iMask % (m_vMax[i] + 1);cur -= vNums[i] * iMul;cur = max(0, cur);iNewMask += iUnit * cur;iMask /= (m_vMax[i] + 1);iUnit *= (m_vMax[i]+1);}return iNewMask;}int NeedGroupCount(const vector<int>& need, const vector<int>& has){int iMax = 0;for (int i = 0; i < m_vMax.size(); i++){if (has[i] <= 0){continue;}iMax = max(iMax,need[i] / has[i]+ (0 != need[i] % has[i]));}return iMax;}
public:int MaskCount()const{return m_iMaskCount;}	int BitCount()const{return m_vMax.size();}
protected:int m_iMaskCount = 1;vector<int> m_vMax;
};class CStrMask : public CMask
{
public:CStrMask(const string& target){vector<int> vCount;for (const auto& ch : target){if (mCharToIndex.count(ch)){vCount[mCharToIndex[ch]]++;}else{mCharToIndex[ch] = vCount.size();vCount.emplace_back(1);}}for (const auto& cnt : vCount){CMask::Add(cnt);}}vector<int> GetVector(const string& s ){vector<int> vCharNums(m_vMax.size());for (const char& ch : s){if (mCharToIndex.count(ch)){auto& i = vCharNums[mCharToIndex[ch]];if (i < m_vMax[mCharToIndex[ch]]){i++;}				}}return vCharNums;}
protected:unordered_map<char, int> mCharToIndex;
private:void Add(int iMax) {};
};

动态规划

动态规划的状态表示

pre[iMask] 表示利用前i-1个贴纸，达到未完成的字符状态为iMask的消耗的最少贴纸数。1000表示无法达成。
dp[iMask] 表示利用前i 个贴纸，达到未完成的字符状态为iMask的消耗的最少贴纸数。

动态规划的转移方程

iPreMask 当前贴纸 使用的贴纸数量 如果状态发生变化，则更新状态。

动态规划的填表顺序

对于每个合法的iPreMask，计算当前贴纸最多需要多少份。三层循环：第一层，枚举各贴纸。第二层，枚举pre各状态。第三层：枚举当前贴纸使用的数量。每次处理还要枚举各字符。
故总时间复杂度为：O(50*2151515)

动态规划的初始状态

pre[iMaskCount-1=0 其它值为1000。

动态规划的返回值

pre[0]

代码

核心代码

class Solution {
public:int minStickers(vector<string>& stickers, string target) {CStrMask mask(target);vector<vector<int>> vMaskToCounts(mask.MaskCount());for (int i = 0; i < mask.MaskCount(); i++){vMaskToCounts[i] = mask.FromMask(i);}vector<int> vPre(mask.MaskCount(), 1000);vPre[mask.MaskCount() - 1] = 0;for (const auto s : stickers){auto vCharNums = mask.GetVector(s);vector<int> dp = vPre;//不选择for (int iPre = 0; iPre < mask.MaskCount(); iPre++){if (vPre[iPre] >= 1000){continue;}const int iSelMax = mask.NeedGroupCount(vMaskToCounts[iPre], vCharNums);for (int iSel = 1; iSel <= iSelMax; iSel++){const int iNewMask = mask.MaskSubVector(iPre, vCharNums, iSel);dp[iNewMask] = min(dp[iNewMask], vPre[iPre] + iSel);}}vPre.swap(dp);}return (vPre[0] >= 1000) ? -1 : vPre[0];}
};

测试用例

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<string> stickers;string target;{Solution sln;stickers = { "travel", "quotient", "nose", "wrote", "any" }, target = "lastwest";auto res = sln.minStickers(stickers, target);Assert(4, res);}{Solution sln;stickers = { "with", "example", "science" }, target = "thehat";auto res = sln.minStickers(stickers, target);Assert(3, res);}{Solution sln;stickers = { "notice", "possible" }, target = "basicbasic";auto res = sln.minStickers(stickers, target);Assert(-1, res);}{Solution sln;stickers = { "right", "ten", "year", "share", "period", "paper", "expect", "village", "home", "happen", "ring", "sat", "even", "afraid", "paint", "self", "range", "camp", "note", "read", "paragraph", "run", "basic", "fill", "week", "his", "star", "power", "any", "colony", "object", "free", "dark", "said", "chick", "true", "glad", "child", "room", "lost", "am", "cry", "quiet", "crease", "while", "race", "fun", "found", "dream", "once" }, target = "materialhalf";auto res = sln.minStickers(stickers, target);Assert(4, res);}{Solution sln;stickers = { "indicate","why","finger","star","unit","board","sister","danger","deal","bit","phrase","caught","if","other","water","huge","general","read","gold","shall","master","men","lay","party","grow","view","if","pull","together","head","thank","street","natural","pull","raise","cost","spoke","race","new","race","liquid","me","please","clear","could","reply","often","huge","old","nor" }, target = "fhhfiyfdcwbycma";auto res = sln.minStickers(stickers, target);Assert(9, res);}}

改进简洁版，性能略差

不区分dp pre，因为一个贴纸可以无限使用。无论是pre[iMask]和dp[iMask] 都可增加贴纸。

动态规划的状态表示

状态压缩：如果target第i位已经贴好，则此位为1；否则此位为0。
dp[iMask] 已经完成iMask 消耗的最少贴纸数。

动态规划的转移方程。

对应每个mask，只需要考虑一个当前贴纸。比如： 目标串为aaa，贴纸为a。状态0只考虑一个贴纸。状态1只考虑1个贴纸，总共2个贴纸。状态3只考虑1个贴纸，总共3个贴纸。
如果目标串有多个相同字符，只需要匹配第一字符。“???” 第一张贴纸后，变成"a??" 不需要考虑“?a?"
方案一：第i步匹配第1个a，第j个步匹配第2个a。
方案二：第i步匹配第2个a，第j个步匹配第1个a。
如果方案二，能达到目标，那方案一显然也能达到目标。
iPreMask等于iNewMask 也不用排除，因为新值比旧值大1，必定被淘汰。

class Solution {
public:int minStickers(vector<string>& stickers, string target) {const int iMaskCount = 1 << target.size();vector<int> dp(iMaskCount, 1000);dp[0] = 0;for (const auto s : stickers){int cnt1[26] = { 0 };for (const auto& ch : s){cnt1[ch - 'a']++;}for (int iPreMask = 0; iPreMask < iMaskCount; iPreMask++){int cnt[26] = { 0 };memcpy(cnt, cnt1, sizeof(cnt1));int iNewMask = iPreMask;for (int j = 0; j < target.size(); j++){if (iPreMask & (1 << j)){continue;//已经拼成}if (cnt[target[j] - 'a']){cnt[target[j] - 'a']--;iNewMask |= (1 << j);}}dp[iNewMask] = min(dp[iNewMask], dp[iPreMask] + 1);}		}return (dp.back() >= 1000) ? -1 : dp.back();}
};

2023年1月第一版

class Solution {
public:
int minStickers(vector& stickers, string target) {
m_target = target;
for (auto& ch : target)
{
m_mTarget[ch]++;
}
std::unordered_set hasMask;
hasMask.insert(0);
std::unordered_map<int,int> preMaskNum;
preMaskNum[0] = 0;
for (auto& s : stickers)
{
std::unordered_map<char, int> mCur;
for (auto& ch : s)
{
if (m_mTarget.count(ch))
{
mCur[ch]++;
}
}
std::unordered_map<int, int> dp = preMaskNum;
const int iCurMask = MakeMask(mCur);
if (hasMask.count(iCurMask))
{
continue;
}
hasMask.insert(iCurMask);
for (const auto& preMask : preMaskNum )
{
std::unordered_map<char, int> mPre;
ParseMask(mPre, preMask.first);
bool bAdd = true;
int iNum = preMask.second;
while (bAdd)
{
bAdd = false;
for (const auto it : mCur)
{
if (m_mTarget[it.first] > mPre[it.first])
{
bAdd = true;
mPre[it.first] = min(m_mTarget[it.first], mPre[it.first] + mCur[it.first]);
}
}
if (bAdd)
{
iNum++;
const int iMask = MakeMask(mPre);
if (dp.count(iMask))
{
dp[iMask] = min(dp[iMask], iNum);
}
else
{
dp[iMask] = iNum;
}
}
}
}
preMaskNum.swap(dp);
}
int iMaskTargt = MakeMask(m_mTarget);
if (preMaskNum.end() == preMaskNum.find(iMaskTargt))
{
return -1;
}
return preMaskNum[iMaskTargt];
}
int MakeMask(const std::unordered_map<char, int>& nums)const
{
int iMask = 0;
for (const auto& mm : m_mTarget )
{
auto it = nums.find(mm.first);
if ((nums.end() != it) && ( it->second > 0 ))
{
iMask = iMask * (mm.second + 1) + min(mm.second, it->second);
}
else
{
iMask = iMask * (mm.second + 1);
}
}
return iMask;
}
void ParseMask(std::unordered_map<char, int>& nums, int iMask)
{
int iMul = 1;
for (auto& it : m_mTarget)
{
iMul *= (it.second+1);
}
for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
{
iMul /= (it->second+1);
nums[it->first] = iMask / iMul;
iMask %= iMul;
}
}
std::string m_target;
std::unordered_map<char, int> m_mTarget;
};

2023年1月第2版

class Solution {
public:
int minStickers(vector& stickers, string target) {
m_target = target;
Init();
vector<std::unordered_map<char, int>> mAllCharNum;
{
std::unordered_set hasMask;
hasMask.insert(0);
for (int i = stickers.size() - 1; i >= 0; i–)
{
std::unordered_map<char, int> mCur;
for (auto& ch : stickers[i])
{
if (m_mTarget.count(ch))
{
mCur[ch]++;
}
}
const int iCurMask = MakeMask(mCur);
if (hasMask.count(iCurMask))
{
continue;
}
hasMask.insert(iCurMask);
mAllCharNum.push_back(mCur);
}
}
std::unordered_set setPreMask,setHasDo;
setPreMask.insert(m_iTargetMask);
setHasDo.insert(m_iTargetMask);
for (int iOpeNum = 1; iOpeNum <= target.length(); iOpeNum++)
{
std::unordered_set dp;
for (auto& preMask : setPreMask)
{
std::unordered_map<char, int> mPre;
ParseMask(mPre, preMask);
for (auto& mCur : mAllCharNum)
{
const int iSubMask = GetSubMask(mPre, mCur);
if (0 == iSubMask)
{
continue;
}
const int iNewMask = preMask - iSubMask;
if (setHasDo.count(iNewMask))
{
continue;
}
if (iNewMask == 0 )
{
return iOpeNum;
}
setHasDo.insert(iNewMask);
dp.insert(iNewMask);
}
}
setPreMask.swap(dp);
vector<std::unordered_map<char, int>> mAllTmp;
for (auto& it : setPreMask)
{
std::unordered_map<char, int> tmp;
ParseMask(tmp, it);
mAllTmp.push_back(tmp);
}
}
return -1;
}
int GetSubMask(const std::unordered_map<char, int>& mPre, const std::unordered_map<char, int>& mCur)
{
int iSubMask = 0;
for (auto& cur : mCur)
{
auto pre = mPre.find(cur.first);
if (pre->second )
{
iSubMask += min(pre->second, cur.second) * m_vCharMul[cur.first-‘a’];
}
}
return iSubMask;
}
int MakeMask(const std::unordered_map<char, int>& nums)const
{
int iMask = 0;
for (const auto& mm : m_mTarget )
{
auto it = nums.find(mm.first);
if ((nums.end() != it) && ( it->second > 0 ))
{
iMask = iMask * (mm.second + 1) + min(mm.second, it->second);
}
else
{
iMask = iMask * (mm.second + 1);
}
}
return iMask;
}
void ParseMask(std::unordered_map<char, int>& nums, int iMask)
{
for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
{
const int iMul = m_vCharMul[it->first-‘a’];
nums[it->first] = iMask / iMul;
iMask %= iMul;
}
}
void Init()
{
for (auto& ch : m_target)
{
m_mTarget[ch]++;
}
m_iTargetMask = MakeMask(m_mTarget);
int iMul = 1;
for (auto& it : m_mTarget)
{
iMul *= (it.second + 1);
}
for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
{
iMul /= (it->second + 1);
m_vCharMul[it->first - ‘a’] = iMul;
}
}
std::string m_target;
int m_iTargetMask;
std::unordered_map<char, int> m_mTarget;
int m_vCharMul[26] ;
};

2023年1月第三版

class Solution {
public:
int minStickers(vector& stickers, string target) {
m_target = target;
Init();

	 vector<std::unordered_map<char, int>> mAllCharNum;{std::unordered_set<int> hasMask;hasMask.insert(0);for (int i = stickers.size() - 1; i >= 0; i--){std::unordered_map<char, int> mCur;for (auto& ch : stickers[i]){if (m_mTarget.count(ch)){mCur[ch]++;}}const int iCurMask = MakeMask(mCur);if (hasMask.count(iCurMask)){continue;}hasMask.insert(iCurMask);mAllCharNum.push_back(mCur);}}std::unordered_set<int> setPreMask,setHasDo;setPreMask.insert(m_iTargetMask);setHasDo.insert(m_iTargetMask);for (int iOpeNum = 1; iOpeNum <= target.length(); iOpeNum++){std::unordered_set<int> dp;for (auto& preMask : setPreMask){std::unordered_map<char, int> mPre;ParseMask(mPre, preMask);char chFristNeedChar = 0;for (auto& it : mPre){if (it.second > 0){chFristNeedChar = it.first;break;}}for (auto& mCur : mAllCharNum){if ((0 == mCur.count(chFristNeedChar)) || (mCur[chFristNeedChar] <= 0 )){continue;}const int iSubMask = GetSubMask(mPre, mCur);if (0 == iSubMask){continue;}const int iNewMask = preMask - iSubMask;if (setHasDo.count(iNewMask)){continue;}if (iNewMask == 0 ){return iOpeNum;}setHasDo.insert(iNewMask);dp.insert(iNewMask);}}setPreMask.swap(dp);vector<std::unordered_map<char, int>> mAllTmp;for (auto& it : setPreMask){std::unordered_map<char, int> tmp;ParseMask(tmp, it); mAllTmp.push_back(tmp);}}return -1;}int GetSubMask(const std::unordered_map<char, int>& mPre, const std::unordered_map<char, int>& mCur){int iSubMask = 0;for (auto& cur : mCur){auto pre = mPre.find(cur.first);if (pre->second ){iSubMask += min(pre->second, cur.second) * m_vCharMul[cur.first-'a'];}}return iSubMask;}int MakeMask(const std::unordered_map<char, int>& nums)const{int iMask = 0;for (const auto& mm : m_mTarget ){auto it = nums.find(mm.first);if ((nums.end() != it) && ( it->second > 0 ))			{iMask = iMask * (mm.second + 1) + min(mm.second, it->second);}else{iMask = iMask * (mm.second + 1);}}return iMask;}void ParseMask(std::unordered_map<char, int>& nums, int iMask){for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it){const int iMul = m_vCharMul[it->first-'a'];nums[it->first] = iMask / iMul;iMask %= iMul;}}void Init(){for (auto& ch : m_target){m_mTarget[ch]++;}m_iTargetMask = MakeMask(m_mTarget);int iMul = 1;for (auto& it : m_mTarget){iMul *= (it.second + 1);}for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it){iMul /= (it->second + 1);m_vCharMul[it->first - 'a'] = iMul;}}std::string m_target;int m_iTargetMask;std::unordered_map<char, int> m_mTarget;int m_vCharMul[26] ;

};

2023年1月 第4版

class CCTestHash
{
public:
std::size_t operator()(const std::unordered_map<char, int>& nums) const
{
return MakeMask(nums);
}
static int MakeMask(const std::unordered_map<char, int>& nums)
{
int iMask = 0;
for (const auto& mm : m_mTarget)
{
auto it = nums.find(mm.first);
if ((nums.end() != it) && (it->second > 0))
{
iMask = iMask * (mm.second + 1) + min(mm.second, it->second);
}
else
{
iMask = iMask * (mm.second + 1);
}
}
return iMask;
}

static void Init(){m_mTarget.clear();for (auto& ch : m_target){m_mTarget[ch]++;}m_iTargetMask = MakeMask(m_mTarget);int iMul = 1;for (auto& it : m_mTarget){iMul *= (it.second + 1);}for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it){iMul /= (it->second + 1);m_vCharMul[it->first - 'a'] = iMul;}}static std::string m_target;
static int m_iTargetMask;
static std::unordered_map<char, int> m_mTarget;
static int m_vCharMul[26];

};
std::string CCTestHash::m_target;
int CCTestHash::m_iTargetMask;
std::unordered_map<char, int> CCTestHash::m_mTarget;
int CCTestHash::m_vCharMul[26];

class Solution {
public:
int minStickers(vector& stickers, string target) {
CCTestHash::m_target = target;
CCTestHash::Init();

	 std::unordered_set<std::unordered_map<char, int>, CCTestHash> hasMask;{			 for (int i = stickers.size() - 1; i >= 0; i--){std::unordered_map<char, int> mCur;for (auto& ch : stickers[i]){if (m_testHask.m_mTarget.count(ch)){mCur[ch]++;}}if (0 == mCur.size()){continue;}if (hasMask.count(mCur)){continue;}hasMask.insert(mCur);}}std::unordered_set<std::unordered_map<char, int>, CCTestHash> setPreMask, setHasDo;setPreMask.insert(CCTestHash::m_mTarget);setHasDo.insert(CCTestHash::m_mTarget);for (int iOpeNum = 1; iOpeNum <= target.length(); iOpeNum++){std::unordered_set<std::unordered_map<char, int>, CCTestHash> dp;for (auto& mPre : setPreMask){char chFristNeedChar = 0;for (auto& it : mPre){if (it.second > 0){chFristNeedChar = it.first;break;}}for (auto& mCur : hasMask){if ((0 == mCur.count(chFristNeedChar)) || (mCur.find(chFristNeedChar)->second <= 0 )){continue;}auto newMask = GetSubMask(mPre, mCur);if (setHasDo.count(newMask)){continue;}if (CCTestHash::MakeMask(newMask) == 0){return iOpeNum;}setHasDo.insert(newMask);dp.insert(newMask);}}setPreMask.swap(dp);}return -1;}std::unordered_map<char, int> GetSubMask(const std::unordered_map<char, int>& mPre, const std::unordered_map<char, int>& mCur){std::unordered_map<char, int> vRet;for (auto& pre : mPre){auto cur = mCur.find(pre.first);if (mCur.end() != cur){vRet[pre.first] = max(0, pre.second - cur->second);}else{vRet[pre.first] = pre.second;}}return vRet;}/*int MakeMask(const std::unordered_map<char, int>& nums)const{int iMask = 0;for (const auto& mm : m_mTarget ){auto it = nums.find(mm.first);if ((nums.end() != it) && ( it->second > 0 ))			{iMask = iMask * (mm.second + 1) + min(mm.second, it->second);}else{iMask = iMask * (mm.second + 1);}}return iMask;}void ParseMask(std::unordered_map<char, int>& nums, int iMask){for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it){const int iMul = m_vCharMul[it->first-'a'];nums[it->first] = iMask / iMul;iMask %= iMul;}}*/CCTestHash m_testHask;

};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。

这篇关于【状态压缩】【动态规划】【C++算法】691贴纸拼词的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/623066。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
hdu1565（状态压缩）

hdu1565（状态压缩）

本人第一道ac的状态压缩dp，这题的数据非常水，很容易过 题意：在n*n的矩阵中选数字使得不存在任意两个数字相邻，求最大值 解题思路： 一、因为在1<<20中有很多状态是无效的，所以第一步是选择有效状态，存到cnt[]数组中 二、dp[i][j]表示到第i行的状态cnt[j]所能得到的最大值，状态转移方程dp[i][j] = max(dp[i][j],dp[i-1][k]) ,其中k满足c
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2