英文网站的首页怎么做,网站建设百度推广总结,wordpress profile,快闪ppt模板免费下载作者推荐
动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本
本文涉及的基础知识点
C算法#xff1a;滑动窗口总结 字典树 map 离线查询
map
map可以分成有序(单调)map和无序(哈希)map。还可分成单键map和多键map#xff08;允许重复的键#xff09;。本文用…作者推荐
动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本
本文涉及的基础知识点
C算法滑动窗口总结 字典树 map 离线查询
map
map可以分成有序(单调)map和无序(哈希)map。还可分成单键map和多键map允许重复的键。本文用单键无序map。
LeetCode2781:最长合法子字符串的长度
给你一个字符串 word 和一个字符串数组 forbidden 。 如果一个字符串不包含 forbidden 中的任何字符串我们称这个字符串是 合法 的。 请你返回字符串 word 的一个 最长合法子字符串 的长度。 子字符串 指的是一个字符串中一段连续的字符它可以为空。 示例 1 输入word “cbaaaabc”, forbidden [“aaa”,“cb”] 输出4 解释总共有 11 个合法子字符串“c”, “b”, “a”, “ba”, “aa”, “bc”, “baa”, “aab”, “ab”, “abc” 和 “aabc”。最长合法子字符串的长度为 4 。 其他子字符串都要么包含 “aaa” 要么包含 “cb” 。 示例 2 输入word “leetcode”, forbidden [“de”,“le”,“e”] 输出4 解释总共有 11 个合法子字符串“l” “t” “c” “o” “d” “tc” “co” “od” “tco” “cod” 和 “tcod” 。最长合法子字符串的长度为 4 。 所有其他子字符串都至少包含 “de” “le” 和 “e” 之一。 参数范围 1 word.length 105 word 只包含小写英文字母。 1 forbidden.length 105 1 forbidden[i].length 10 forbidden[i] 只包含小写英文字母。
滑动窗口离线查询map
时间复杂度(nmmnlognn)。m max(forbidden[i].length)为10 第一步如果s[left,right]等于 forbidden中任何一个字符串记录在vLeftRight中。本问题等效与不能包括任意[left,right]的最长子串。 第二步排序vLeftRight。 第三步从大到小枚举合法子串的左边界i计算最大右边界j。 如果s[left,right]等于某个禁止串
lefti无论j为何值都不会包括对应的禁止串因为s[left]不在对应的子串中leftij的取值范围为[i,right)不能取值right 否则s[left,right] 就在word[i,j]中。如果多个无法合法的right取最小值。如果没有合法的right取m_c。
离线查询
由于vLeftRight 已经按left排序每次处理i之前先用left i的right更新iMin。
代码
核心代码
class Solution {
public:int longestValidSubstring(string word, vectorstring forbidden) {m_c word.length();std::unordered_setstring setHas(forbidden.begin(), forbidden.end());vectorpairint, int vLeftRight;for (int len 1; len 10; len){for (int left 0; left len m_c; left){if (setHas.count(word.substr(left, len))){vLeftRight.emplace_back(left, left len - 1);}}}sort(vLeftRight.begin(), vLeftRight.end());int iRet 0;int iMin m_c;for (int i m_c - 1; i 0; i--){while (vLeftRight.size() (vLeftRight.back().first i)){iMin min(iMin, vLeftRight.back().second);vLeftRight.pop_back();}iRet max(iRet, iMin - i);}return iRet;}int m_c;
};字典树
可以利用字典树将第一步的时间复杂度降到O(nm)。
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);}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 };
};class Solution {
public:int longestValidSubstring(string word, vectorstring forbidden) {m_c word.length();CTriechar,a trie;for (const auto s : forbidden){trie.Add(s.begin(), s.end());}vectorpairint, int vLeftRight;for (int left 0; left m_c ; left){CTriechar,a* p trie;for (int len 1; left len m_c; len){p p-GetChild(word[left len - 1]);if (nullptr p){break;}if (p-m_iLeafID 0){vLeftRight.emplace_back(left, left len - 1);}}}sort(vLeftRight.begin(), vLeftRight.end());int iRet 0;int iMin m_c;for (int i m_c - 1; i 0; i--){while (vLeftRight.size() (vLeftRight.back().first i)){iMin min(iMin, vLeftRight.back().second);vLeftRight.pop_back();}iRet max(iRet, iMin - i);}return iRet;}int m_c;
};2023年7月版
class Solution { public: int longestValidSubstring(string word, vector forbidden) { m_pHash std::make_shared CHashStr(word,26); std::unordered_set setCode[11]; for (const string s : forbidden) { const int len s.length(); CHashStr hash(s,26); auto llCode hash.GetHashExincludeRight(len); setCode[len].emplace(llCode); } std::mapint, int mEndLen; for (int i 0; i word.size(); i) { for (int len 1; len 10 ; len) { const int end i len; if (end word.size()) { continue; } int llCode m_pHash-GetHashExincludeRight(i, end); if (setCode[len].end() ! setCode[len].find(llCode)) { //目标串不能包括[1,ilen) mEndLen[ilen] len; break; } } } int begin 0; int iMaxLen 0; for (const auto it : mEndLen) { const int iCurLen it.first - begin-1; iMaxLen max(iMaxLen, iCurLen); begin max(begin,it.first - it.second 1); } iMaxLen max(iMaxLen, (int)word.size() - begin); return iMaxLen; } std::shared_ptr CHashStr m_pHash; }; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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**实现。
