深圳市官网网站建设哪家好一键生成app的方法

当前位置： 首页 > news >正文

深圳市官网网站建设哪家好,一键生成app的方法,网站建设优化排名推广,百度网站收录查询地址作者推荐 【动态规划】【数学】【C算法】18赛车 本文涉及知识点 状态压缩 动态规划 LeetCode:691 贴纸拼词 我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。 您想要拼写出给定的字符串 target #xff0c;方法是从收集的贴纸中切割单个字母并重新排列它们。如…作者推荐 【动态规划】【数学】【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为(mvMax[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);}vectorint FromMask(int iMask){vectorint 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 vectorint vNums,int iMul1){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 vectorint 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 vectorint need, const vectorint has){int iMax 0;for (int i 0; i m_vMax.size(); i){if (has[i] 0){continue;}iMax max(iMax,need[i] / hasi);}return iMax;} public:int MaskCount()const{return m_iMaskCount;} int BitCount()const{return m_vMax.size();} protected:int m_iMaskCount 1;vectorint m_vMax; };class CStrMask : public CMask { public:CStrMask(const string target){vectorint 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);}}vectorint GetVector(const string s ){vectorint 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_mapchar, 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-10 其它值为1000。 动态规划的返回值 pre[0] 代码 核心代码 class Solution { public:int minStickers(vectorstring stickers, string target) {CStrMask mask(target);vectorvectorint vMaskToCounts(mask.MaskCount());for (int i 0; i mask.MaskCount(); i){vMaskToCounts[i] mask.FromMask(i);}vectorint vPre(mask.MaskCount(), 1000);vPre[mask.MaskCount() - 1] 0;for (const auto s : stickers){auto vCharNums mask.GetVector(s);vectorint 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];} };测试用例 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() {vectorstring 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(vectorstring stickers, string target) {const int iMaskCount 1 target.size();vectorint 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_mapint,int preMaskNum; preMaskNum[0] 0; for (auto s : stickers) { std::unordered_mapchar, int mCur; for (auto ch : s) { if (m_mTarget.count(ch)) { mCur[ch]; } } std::unordered_mapint, int dp preMaskNum; const int iCurMask MakeMask(mCur); if (hasMask.count(iCurMask)) { continue; } hasMask.insert(iCurMask); for (const auto preMask : preMaskNum ) { std::unordered_mapchar, 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_mapchar, 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_mapchar, int nums, int iMask) { int iMul 1; for (auto it : m_mTarget) { iMul * (it.second1); } for (auto it m_mTarget.begin(); it ! m_mTarget.end(); it) { iMul / (it-second1); nums[it-first] iMask / iMul; iMask % iMul; } } std::string m_target; std::unordered_mapchar, int m_mTarget; }; 2023年1月第2版 class Solution { public: int minStickers(vector stickers, string target) { m_target target; Init(); vectorstd::unordered_mapchar, int mAllCharNum; { std::unordered_set hasMask; hasMask.insert(0); for (int i stickers.size() - 1; i 0; i–) { std::unordered_mapchar, 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_mapchar, 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); vectorstd::unordered_mapchar, int mAllTmp; for (auto it : setPreMask) { std::unordered_mapchar, int tmp; ParseMask(tmp, it); mAllTmp.push_back(tmp); } } return -1; } int GetSubMask(const std::unordered_mapchar, int mPre, const std::unordered_mapchar, 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_mapchar, 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_mapchar, 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_mapchar, int m_mTarget; int m_vCharMul[26] ; }; 2023年1月第三版 class Solution { public: int minStickers(vector stickers, string target) { m_target target; Init(); vectorstd::unordered_mapchar, int mAllCharNum;{std::unordered_setint hasMask;hasMask.insert(0);for (int i stickers.size() - 1; i 0; i–){std::unordered_mapchar, 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_setint setPreMask,setHasDo;setPreMask.insert(m_iTargetMask);setHasDo.insert(m_iTargetMask);for (int iOpeNum 1; iOpeNum target.length(); iOpeNum){std::unordered_setint dp;for (auto preMask : setPreMask){std::unordered_mapchar, 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);vectorstd::unordered_mapchar, int mAllTmp;for (auto it : setPreMask){std::unordered_mapchar, int tmp;ParseMask(tmp, it); mAllTmp.push_back(tmp);}}return -1;}int GetSubMask(const std::unordered_mapchar, int mPre, const std::unordered_mapchar, 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_mapchar, 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_mapchar, 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_mapchar, int m_mTarget;int m_vCharMul[26] ;}; 2023年1月 第4版 class CCTestHash { public: std::size_t operator()(const std::unordered_mapchar, int nums) const { return MakeMask(nums); } static int MakeMask(const std::unordered_mapchar, 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_mapchar, int m_mTarget; static int m_vCharMul[26];}; std::string CCTestHash::m_target; int CCTestHash::m_iTargetMask; std::unordered_mapchar, 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_setstd::unordered_mapchar, int, CCTestHash hasMask;{ for (int i stickers.size() - 1; i 0; i–){std::unordered_mapchar, 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_setstd::unordered_mapchar, int, CCTestHash setPreMask, setHasDo;setPreMask.insert(CCTestHash::m_mTarget);setHasDo.insert(CCTestHash::m_mTarget);for (int iOpeNum 1; iOpeNum target.length(); iOpeNum){std::unordered_setstd::unordered_mapchar, 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_mapchar, int GetSubMask(const std::unordered_mapchar, int mPre, const std::unordered_mapchar, int mCur){std::unordered_mapchar, 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_mapchar, 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_mapchar, 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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用C实现。