嘉兴网站制作优化,全屋定制设计软件哪个好,wordpress 4.9.6 主题,游戏工作室网络组建方案涉及知识点
动态规划 多源最短路径 字典树
题目
给你两个下标从 0 开始的字符串 source 和 target #xff0c;它们的长度均为 n 并且由 小写 英文字母组成。 另给你两个下标从 0 开始的字符串数组 original 和 changed #xff0c;以及一个整数数组 cost #xff0c;其中…涉及知识点
动态规划 多源最短路径 字典树
题目
给你两个下标从 0 开始的字符串 source 和 target 它们的长度均为 n 并且由 小写 英文字母组成。 另给你两个下标从 0 开始的字符串数组 original 和 changed 以及一个整数数组 cost 其中 cost[i] 代表将字符串 original[i] 更改为字符串 changed[i] 的成本。 你从字符串 source 开始。在一次操作中如果 存在 任意 下标 j 满足 cost[j] z 、original[j] x 以及 changed[j] y 你就可以选择字符串中的 子串 x 并以 z 的成本将其更改为 y 。 你可以执行 任意数量 的操作但是任两次操作必须满足 以下两个 条件 之一 在两次操作中选择的子串分别是 source[a…b] 和 source[c…d] 满足 b c 或 d a 。换句话说两次操作中选择的下标 不相交 。 在两次操作中选择的子串分别是 source[a…b] 和 source[c…d] 满足 a c 且 b d 。换句话说两次操作中选择的下标 相同 。 返回将字符串 source 转换为字符串 target 所需的 最小 成本。如果不可能完成转换则返回 -1 。 注意可能存在下标 i 、j 使得 original[j] original[i] 且 changed[j] changed[i] 。 示例 1 输入source “abcd”, target “acbe”, original [“a”,“b”,“c”,“c”,“e”,“d”], changed [“b”,“c”,“b”,“e”,“b”,“e”], cost [2,5,5,1,2,20] 输出28 解释将 “abcd” 转换为 “acbe”执行以下操作
将子串 source[1…1] 从 “b” 改为 “c” 成本为 5 。将子串 source[2…2] 从 “c” 改为 “e” 成本为 1 。将子串 source[2…2] 从 “e” 改为 “b” 成本为 2 。将子串 source[3…3] 从 “d” 改为 “e” 成本为 20 。 产生的总成本是 5 1 2 20 28 。 可以证明这是可能的最小成本。 示例 2 输入source “abcdefgh”, target “acdeeghh”, original [“bcd”,“fgh”,“thh”], changed [“cde”,“thh”,“ghh”], cost [1,3,5] 输出9 解释将 “abcdefgh” 转换为 “acdeeghh”执行以下操作将子串 source[1…3] 从 “bcd” 改为 “cde” 成本为 1 。将子串 source[5…7] 从 “fgh” 改为 “thh” 成本为 3 。可以执行此操作因为下标 [5,7] 与第一次操作选中的下标不相交。将子串 source[5…7] 从 “thh” 改为 “ghh” 成本为 5 。可以执行此操作因为下标 [5,7] 与第一次操作选中的下标不相交且与第二次操作选中的下标相同。 产生的总成本是 1 3 5 9 。 可以证明这是可能的最小成本。 示例 3 输入source “abcdefgh”, target “addddddd”, original [“bcd”,“defgh”], changed [“ddd”,“ddddd”], cost [100,1578] 输出-1 解释无法将 “abcdefgh” 转换为 “addddddd” 。 如果选择子串 source[1…3] 执行第一次操作以将 “abcdefgh” 改为 “adddefgh” 你无法选择子串 source[3…7] 执行第二次操作因为两次操作有一个共用下标 3 。 如果选择子串 source[3…7] 执行第一次操作以将 “abcdefgh” 改为 “abcddddd” 你无法选择子串 source[1…3] 执行第二次操作因为两次操作有一个共用下标 3 。 参数范围 1 source.length target.length 1000 source、target 均由小写英文字母组成 1 cost.length original.length changed.length 100 1 original[i].length changed[i].length source.length original[i]、changed[i] 均由小写英文字母组成 original[i] ! changed[i] 1 cost[i] 106
分析
将s按顺序拆分成若干子串任何字符都在一个子串中且只在一个字串中。求这些子串全部转成t的最小成本。
动态规划
动态规划之状态表示dp[i]表示将s[0,i)转化成t[0,i)的最小成本动态规划之状态转移方程dp[j]min(dp[i]s[i,j)转化成t[i,j)成本), i取值范围[0,j)动态规划之状态之初始化dp[0]0动态规划之状态之填表顺序两层循环枚举i,j 先枚举i,再枚举j。s[i,j)是最后一个子串动态规划之状态之返回值dp.back()
字符经过多次转化的最小成本
本质就是最短多源路径。
将字符串转成整数节点编号
如果用哈希map每次是O(n)就超时了。可以自写哈希或用字典树从查询s[i,j)到s[ij1)时间复杂度是O(1)。总时间复杂度是O(n2)。
测试用例
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()
{string source, target;vectorstring original, changed;vectorint cost;{Solution sln;source abcdefgh, target acdeeghh, original { bcd, fgh, thh }, changed { cde, thh, ghh }, cost { 1, 3, 5 };auto res sln.minimumCost(source, target, original, changed, cost);Assert(9LL, res);}{Solution sln;source abcd, target acbe;original { a, b, c, c, e, d }, changed { b, c, b, e, b, e };cost { 2, 5, 5, 1, 2, 20 };auto res sln.minimumCost(source, target, original, changed, cost);Assert(28LL, res);}{Solution sln;source abbaacddcbacbddcbdbddcadbadbbdbaabcdbdbdcaccacaddcabadadaccabbddbbdacaacdbdcaaddcacbcbcaaacaddabcabc;target abbaacdbcbabcadcbdbddcadbadbbddaabcdbdddcacadbacabcbdbbbbdaabbddbbdaabbcdbdcaaddcacbcbcadadccdcbcbcb;original { b, c, a, cbd, adc, ddb, dcb, dbd, b, caac, acdc, cbbd, bcdb, ddbc, aacadda, cbadbbd, aaabcad, bacdccc, ddabdaa, abc, bbc, cdd, ddb, cacaddcabad, bdcdccabdcb, bddbbabdcac, adacc, bbdca, dabad, cddcba };changed { c, a, d, adc, ddb, dcb, dbd, bca, d, acdc, cbbd, bcdb, ddbc, abbc, cbadbbd, aaabcad, bacdccc, ddabdaa, dadccdc, bbc, cdd, ddb, bcb, bdcdccabdcb, bddbbabdcac, adbacabcbdb, bbdca, dabad, bbbda, cdbcba };cost { 63, 87, 77, 94, 100, 73, 99, 16, 89, 94, 76, 43, 76, 84, 83, 38, 96, 87, 34, 98, 33, 53, 58, 90, 61, 51, 92, 76, 91, 70 };auto res sln.minimumCost(source, target, original, changed, cost);Assert(2044LL, res);}{Solution sln;source aaaddcaaccbabaaccbabbaadcccadbaacbddbaccabddbdbaaddbbacbddddbbdbccaadcaccacdbcbddbacabadaaccbadbbdbc;target abaddcabcdbabcbadcaccaadabbadddbcacaaabdabbdcbbdbcbaaabbbcddcbddcbccadacddcbdcbacadbbadbdabcbadbbdac;original { ddddb, dccbb, dadac, dbdbb, ddbacabadaac, bcbccdcadabd, dacabcdaacca, dcdadacacbbd, dcccadbaacbddbacc, dcdcbccdccdbaaaac, bbbcccdbcdcadaabc, bccaadcaccacdb, bbcabcbcbaddbd, dbadadaddcddad, badaddbcddacca, bc, da, cb, ddbdbaaddbbac, dbcadcdbabddd, abdadacbbbcca, adaaabcabdbcc, caaccbabaaccbabba, abaadddbaaccbbacc, bbddaaadcbccccbac, cdbdbddaadbbbdbdd, bcbdaabaddbdcdcaa, aa, cb, dd };changed { dccbb, dadac, dbdbb, bcddc, bcbccdcadabd, dacabcdaacca, dcdadacacbbd, acadbbadbdab, dcdcbccdccdbaaaac, bbbcccdbcdcadaabc, dabbadddbcacaaabd, bbcabcbcbaddbd, dbadadaddcddad, badaddbcddacca, dcbccadacddcbd, da, cb, ac, dbcadcdbabddd, abdadacbbbcca, adaaabcabdbcc, bdcbbdbcbaaab, abaadddbaaccbbacc, bbddaaadcbccccbac, cdbdbddaadbbbdbdd, bcbdaabaddbdcdcaa, cabcdbabcbadcacca, cb, dd, ba };cost { 67, 56, 64, 83, 100, 73, 95, 97, 100, 98, 20, 92, 58, 70, 95, 77, 95, 93, 69, 92, 77, 53, 96, 68, 83, 96, 93, 64, 81, 100 };auto res sln.minimumCost(source, target, original, changed, cost);Assert(2405LL, res);}//CConsole::Out(res);
}代码
我写了N版都超时单个用例不超时总用例超时。用题解的代码运行了错误和超时用例速度比我的速度快了近一半。算了不继续优化了许多比赛的技巧是工作的灾难比如用原生数组代替vector。
第六版超时
templateclass TData, TData defData,int iTypeNum 26, TData cBegin a
class CTrie
{
public:CTrie() {m_iID s_ID;}int GetLeadCount(){return m_iLeafCount;}templateclass ITint Add(IT begin, IT end){int iLeve 0;CTrie* pNode this;for (; begin ! end; begin){pNode pNode-AddChar(*begin); pNode-m_iLeve iLeve;}if (-1 pNode-m_iLeafID){pNode-m_iLeafID m_iLeafCount;}return pNode-m_iLeafID;}templateclass ITCTrie* Search(IT begin, IT end){if (begin end){return this;}if (. *begin){for (auto ptr : m_vPChilds){if (!ptr){continue;}auto pSearch ptr-Search(begin 1, end);if (pSearch){return pSearch;}}return nullptr;}auto ptr GetChild(*begin);if (nullptr ptr){return nullptr;}return ptr-Search(begin 1, end);}TData m_data defData;CTrie* AddChar(TData ele){if ((ele cBegin) || (ele cBegin iTypeNum)){return nullptr;}const int index ele - cBegin;auto ptr m_vPChilds[index];if (!ptr){m_vPChilds[index] new CTrie();}return m_vPChilds[index];}CTrie* GetChild(TData ele)const{if ((ele cBegin) || (ele cBegin iTypeNum)){return nullptr;}return m_vPChilds[ele - cBegin];}
protected:int m_iID;
public:int m_iLeafID-1;
protected:int m_iLeve-1;inline static int s_ID 0;int m_iLeafCount 0;CTrie* m_vPChilds[iTypeNum] { nullptr };
};templatechar defDataa, int iTypeNum 26, char cBegin a
class CStrTrieHelp
{
public:int Add(const string s){return m_trie.Add(s.begin(), s.begin() s.length());}CTriechar, defData, iTypeNum, cBegin* Search(const string s){return m_trie.Search(s.begin(), s.begin() s.length());}CTriechar, defData, iTypeNum, cBegin* SearchSub(const string s,int iPos,int len){return m_trie.Search(s.begin() iPos, s.begin() iPos len );}CTriechar, defData, iTypeNum, cBegin m_trie;
};
templatechar defData a, int iTypeNum 26, char cBegin a
class CStrIndexs
{
public:void Add(const string s){m_trie.Add(s);}int Seach(const string s){auto p m_trie.Search(s);if (nullptr p){return -1;}return p-m_iLeafID;}int SearchSub(const string s, int iPos, int len){auto p m_trie.SearchSub(s, iPos, len);if (nullptr p){return -1;}return p-m_iDebug;}CStrTrieHelpdefData, iTypeNum, cBegin m_trie;
};//多源码路径
templateclass T,T INF 1000*1000*1000
class CFloyd
{
public:CFloyd(const vectorvectorT mat){m_vMat mat;const int n mat.size();for (int i 0; i n; i){//通过i中转for (int i1 0; i1 n; i1){for (int i2 0; i2 n; i2){//此时m_vMat[i1][i2] 表示通过[0,i)中转的最短距离m_vMat[i1][i2] min(m_vMat[i1][i2], m_vMat[i1][i] m_vMat[i][i2]);//m_vMat[i1][i2] 表示通过[0,i]中转的最短距离}}} };vectorvectorT m_vMat;
};class Solution {
public:long long minimumCost(string source, string target, vectorstring original, vectorstring changed, vectorint cost) {CStrIndexs strIndexs;for (const auto s : original){strIndexs.Add(s);}for (const auto s : changed){strIndexs.Add(s);}const int iNotMay 1000 * 1000 * 1000;vectorvectorint vMat(strIndexs.m_trie.m_trie.GetLeadCount(), vectorint(strIndexs.m_trie.m_trie.GetLeadCount(), iNotMay));for (int j 0; j original.size(); j){const int iSrc strIndexs.Seach(original[j]);const int iDest strIndexs.Seach(changed[j]); auto n vMat[iSrc][iDest];n min(n, cost[j]);}for (int i 0; i strIndexs.m_trie.m_trie.GetLeadCount(); i){vMat[i][i] 0;}CFloyd floyd(vMat);vectorlong long vRet(source.length() 1, LLONG_MAX / 1000);vRet[0] 0;for (int i 0; i source.length(); i){bool bSame true;auto pSrc strIndexs.m_trie.m_trie;auto pDst strIndexs.m_trie.m_trie;for (int len 1; len i source.length(); len){const char ch1 source[len i - 1];const char ch2 target[len i - 1]; bSame (ch1 ch2);if (nullptr ! pSrc){pSrc pSrc-GetChild(ch1);}if (nullptr ! pDst){pDst pDst-GetChild(ch2);}if (bSame){vRet[i len] min(vRet[i len], vRet[i]);continue;} if ((nullptr pSrc) || (nullptr pDst)){break;}const int iSrc pSrc-m_iLeafID;const int iDest pDst-m_iLeafID;if ((-1 iSrc) || (-1 iDest)){continue;}const int iDist floyd.m_vMat[iSrc][iDest];if (iDist iNotMay){continue;}vRet[i len] min(vRet[i len], vRet[i] iDist);}}return (vRet.back() LLONG_MAX / 1000) ? -1 : vRet.back();}
};第一版超时
//多源码路径 templateclass T,T INF 100010001000 class CFloyd { public: CFloyd(const vectorvector mat) { m_vMat mat; const int n mat.size(); for (int i 0; i n; i) {//通过i中转 for (int i1 0; i1 n; i1) { for (int i2 0; i2 n; i2) { //此时m_vMat[i1][i2] 表示通过[0,i)中转的最短距离 m_vMat[i1][i2] min(m_vMat[i1][i2], m_vMat[i1][i] m_vMat[i][i2]); //m_vMat[i1][i2] 表示通过[0,i]中转的最短距离 } } } }; vectorvector m_vMat; };
class Solution { public: long long minimumCost(string source, string target, vector original, vector changed, vector cost) { vector strs(original.begin(), original.end()); strs.insert(strs.end(), changed.begin(), changed.end()); sort(strs.begin(),strs.end()); strs.erase(std::unique(strs.begin(), strs.end()), strs.end()); std::unordered_mapstring, int mStrToNode; for (int i 0; i strs.size(); i) { mStrToNode[strs[i]] i; } const int iNotMay 1000 * 1000 * 1000; vectorvector vMat(strs.size(), vector(strs.size(), iNotMay)); vector vOriNode; for (int j 0; j original.size(); j) { vOriNode.emplace_back(mStrToNode[original[j]]); auto n vMat[vOriNode.back()][mStrToNode[changed[j]]]; n min(n,cost[j]); } for (int i 0; i strs.size(); i) { vMat[i][i] 0; } CFloyd floyd(vMat); vector vRet(source.length() 1,LLONG_MAX/1000 ); vRet[0]0; for (int i 0; i source.length(); i) { if (source[i] target[i]) { vRet[i 1] min(vRet[i1],vRet[i]); //continue; 相等也可以替换 } for (int j 0; j original.size(); j) { const int len original[j].length(); if (i len source.length()) { continue; } if (source.substr(i, len) ! original[j]) { continue; } string sDst target.substr(i, len); if (!mStrToNode.count(sDst)) { continue; } const int iDest mStrToNode[sDst]; const int iDist floyd.m_vMat[vOriNode[j]][iDest]; if (iDist iNotMay) { continue; } vRet[i len] min(vRet[i len],vRet[i]iDist); } } return (vRet.back() LLONG_MAX / 1000) ? -1 : vRet.back(); } };
第二版超时
//多源码路径 templateclass T,T INF 100010001000 class CFloyd { public: CFloyd(const vectorvector mat) { m_vMat mat; const int n mat.size(); for (int i 0; i n; i) {//通过i中转 for (int i1 0; i1 n; i1) { for (int i2 0; i2 n; i2) { //此时m_vMat[i1][i2] 表示通过[0,i)中转的最短距离 m_vMat[i1][i2] min(m_vMat[i1][i2], m_vMat[i1][i] m_vMat[i][i2]); //m_vMat[i1][i2] 表示通过[0,i]中转的最短距离 } } } }; vectorvector m_vMat; };
class Solution { public: long long minimumCost(string source, string target, vector original, vector changed, vector cost) { vector strs(original.begin(), original.end()); strs.insert(strs.end(), changed.begin(), changed.end()); sort(strs.begin(),strs.end()); strs.erase(std::unique(strs.begin(), strs.end()), strs.end()); std::unordered_mapstring, int mStrToNode; for (int i 0; i strs.size(); i) { mStrToNode[strs[i]] i; } const int iNotMay 1000 * 1000 * 1000; vectorvector vMat(strs.size(), vector(strs.size(), iNotMay)); for (int j 0; j original.size(); j) { auto n vMat[mStrToNode[original[j]]][mStrToNode[changed[j]]]; n min(n,cost[j]); } for (int i 0; i strs.size(); i) { vMat[i][i] 0; } CFloyd floyd(vMat); vector vRet(source.length() 1,LLONG_MAX/1000 ); vRet[0]0; for (int i 0; i source.length(); i) { for (int len 1; len i source.length(); len) { const string sSrc source.substr(i, len); const string sDst target.substr(i, len); if (sSrc sDst) { vRet[i len] min(vRet[i len], vRet[i] ); continue; } if (!mStrToNode.count(sDst)|| !mStrToNode.count(sSrc)) { continue; } const int iSrc mStrToNode[sSrc]; const int iDest mStrToNode[sDst]; const int iDist floyd.m_vMat[iSrc][iDest]; if (iDist iNotMay) { continue; } vRet[i len] min(vRet[i len], vRet[i] iDist); } } return (vRet.back() LLONG_MAX / 1000) ? -1 : vRet.back(); } };
第四版超时
templateclass TData, TData defData,int iTypeNum 26, TData cBegin ‘a’ class CTrie { public: CTrie() {
}
templateclass IT
CTrie* Add(IT begin, IT end,const int iDebug)
{int iLeve 0;CTrie* pNode this;for (; begin ! end; begin){pNode pNode-AddChar(*begin); pNode-m_iLeve iLeve;}pNode-m_iDebug iDebug;return pNode;
}
templateclass IT
CTrie* Search(IT begin, IT end)
{if (begin end){return this;}if (. *begin){for (auto ptr : m_vPChilds){if (!ptr){continue;}auto pSearch ptr-Search(begin 1, end);if (pSearch){return pSearch;}}return nullptr;}auto ptr GetChild(*begin);if (nullptr ptr){return nullptr;}return ptr-Search(begin 1, end);
}
TData m_data defData;CTrie* AddChar(TData ele)
{if ((ele cBegin) || (ele cBegin iTypeNum)){return nullptr;}const int index ele - cBegin;auto ptr m_vPChilds[index];if (!ptr){m_vPChilds[index] new CTrie();}return m_vPChilds[index];
}CTrie* GetChild(TData ele)const
{if ((ele cBegin) || (ele cBegin iTypeNum)){return nullptr;}return m_vPChilds[ele - cBegin];
}int m_iDebug-1;protected: int m_iLeve-1; CTrie* m_vPChilds[iTypeNum] { nullptr }; };
templatechar defData, int iTypeNum 26, char cBegin ‘a’ class CStrTrieHelp { public: CTriechar, defData, iTypeNum, cBegin* Add(const string s,int iDebug) { return m_trie.Add(s.begin(), s.begin() s.length(), iDebug); } CTriechar, defData, iTypeNum, cBegin* Search(const string s) { return m_trie.Search(s.begin(), s.begin() s.length()); } CTriechar, defData, iTypeNum, cBegin* SearchSub(const string s,int iPos,int len) { return m_trie.Search(s.begin() iPos, s.begin() iPos len ); } CTriechar, defData, iTypeNum, cBegin m_trie; }; templatechar defData ‘a’, int iTypeNum 26, char cBegin ‘a’ class CStrIndexs { public: void Add(const string s, int iDebug) { m_trie.Add(s, iDebug); } int Seach(const string s) { auto p m_trie.Search(s); if (nullptr p) { return -1; } return p-m_iDebug; } int SearchSub(const string s, int iPos, int len) { auto p m_trie.SearchSub(s, iPos, len); if (nullptr p) { return -1; } return p-m_iDebug; } protected: CStrTrieHelpdefData, iTypeNum, cBegin m_trie; };
//多源码路径 templateclass T,T INF 100010001000 class CFloyd { public: CFloyd(const vectorvector mat) { m_vMat mat; const int n mat.size(); for (int i 0; i n; i) {//通过i中转 for (int i1 0; i1 n; i1) { for (int i2 0; i2 n; i2) { //此时m_vMat[i1][i2] 表示通过[0,i)中转的最短距离 m_vMat[i1][i2] min(m_vMat[i1][i2], m_vMat[i1][i] m_vMat[i][i2]); //m_vMat[i1][i2] 表示通过[0,i]中转的最短距离 } } } }; vectorvector m_vMat; };
class Solution { public: long long minimumCost(string source, string target, vector original, vector changed, vector cost) { vector strs(original.begin(), original.end()); strs.insert(strs.end(), changed.begin(), changed.end()); sort(strs.begin(), strs.end()); strs.erase(std::unique(strs.begin(), strs.end()), strs.end()); CStrIndexs strIndexs; for (int i 0; i strs.size(); i) { strIndexs.Add(strs[i], i); } const int iNotMay 1000 * 1000 * 1000; vectorvector vMat(strs.size(), vector(strs.size(), iNotMay)); for (int j 0; j original.size(); j) { const int iSrc strIndexs.Seach(original[j]); const int iDest strIndexs.Seach(changed[j]); auto n vMat[iSrc][iDest]; n min(n, cost[j]); } for (int i 0; i strs.size(); i) { vMat[i][i] 0; } CFloyd floyd(vMat); vector vRet(source.length() 1, LLONG_MAX / 1000); vRet[0] 0; for (int i 0; i source.length(); i) { bool bSame true; for (int len 1; len i source.length(); len) { bSame (source[len i - 1] target[len i - 1]); if (bSame) { vRet[i len] min(vRet[i len], vRet[i]); continue; } const int iSrc strIndexs.SearchSub(source, i, len); const int iDest strIndexs.SearchSub(target, i, len); if ((-1 iSrc) || (-1 iDest)) { continue; } const int iDist floyd.m_vMat[iSrc][iDest]; if (iDist iNotMay) { continue; } vRet[i len] min(vRet[i len], vRet[i] iDist); } } return (vRet.back() LLONG_MAX / 1000) ? -1 : vRet.back(); } }; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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 实现。
