作者推荐
【二叉树】【单调双向队列】LeetCode239:滑动窗口最大值
本文涉及的基础知识点
C++算法：滑动窗口总结
题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。 注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串，我们保证它是唯一的答案。 示例 1： 输入：s = “ADOBECODEBANC”, t = “ABC” 输出：“BANC” 解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。 示例 2： 输入：s = “a”, t = “a” 输出：“a” 解释：整个字符串 s 是最小覆盖子串。 示例 3: 输入: s = “a”, t = “aa” 输出: “” 解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。 参数范围： m == s.length n == t.length 1 <= m, n <= 105 s 和 t 由英文字母组成
滑动窗口
** 时间复杂度** : O(n+m)。两层循环，分别枚举子数组起点和终点[i,right)，由于right不归0，所以总时间复杂度是O(n)。
CContain
m_mNeedCharCount记录了t中各字符的数量，m_mHasCharCount记录了枚举的子串各字符的数量。m_iNotSameCharCount 记录了m_mHasCharCount有多少个字符的数量少于m_mNeedCharCount。m_iNotSameCharCount为0，表示此子串符合题意。
增加前ch的数量符合题意增加后ch的数量符合题意增加前ch的数量不符合题意增加后ch的数量不符合题意增加前ch的数量不符合题意增加后ch的数量符合题意增加前ch的数量符合题意增加后ch的数量不符合题意
iAdd可以为1或-1 将m_iNotSameCharCount改名m_iLessCharCount更符合题意。
滑动窗口
CContain 记录[i,right1)，让它记录[i,right1+1)，只需要将s[right1]加进去就可以了。 CContain 记录[i,right1)，让它记录[i+1,right1)，只需要减去s[i]就可以了。 [i,right) 是符合题意的最小值，也就是[i,right-1)不符合题意，[i+1,right-1)也必定不符合题意。所以无需尝试[i+1,right-1)。即right无需归0（复位）。
代码
核心代码
class CContain
{
public:
CContain(const string& t)
{
for (const auto& ch : t)
{
m_mNeedCharCount[ch]++;
}
m_iNotSameCharCount = m_mNeedCharCount.size();
}
void Add(const char& ch,int iAdd)
{
if (m_mNeedCharCount.count(ch)&&(m_mHasCharCount[ch] >= m_mNeedCharCount[ch] ))
{
m_iNotSameCharCount++;
}
m_mHasCharCount[ch] += iAdd;
if (m_mNeedCharCount.count(ch) && (m_mHasCharCount[ch] >= m_mNeedCharCount[ch]))
{
m_iNotSameCharCount--;
}
}
bool IsAllContain()
{
return 0 == m_iNotSameCharCount;
}
protected:
std::unordered_map
int m_iNotSameCharCount = 0;
};
class Solution {
public:
string minWindow(string s, string t) {
CContain test(t);
int iMaxLen = INT_MAX;
int iPos =0;
for (int i = 0, right = 0; i < s.length(); i++)
{
for(;(right < s.length())&&(!test.IsAllContain());right++)
{
test.Add(s[right],1);
}
if (test.IsAllContain())
{
if (right - i < iMaxLen)
{
iMaxLen = right - i;
iPos = i;
}
}
test.Add(s[i], -1);
}
if (INT_MAX == iMaxLen)
{
iMaxLen = 0;
}
return s.substr(iPos, iMaxLen);
}
};
测试用例
template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template
void Assert(const vector
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
string s,t;
{
Solution sln;
s = "a", t = "a";
auto res = sln.minWindow(s, t);
Assert(std::string("a"), res);
}
{
Solution sln;
s = "ADOBECODEBANC", t = "ABC";
auto res = sln.minWindow(s, t);
Assert(std::string("BANC"), res);
}
{
Solution sln;
s = "a", t = "aa";
auto res = sln.minWindow(s, t);
Assert(std::string(""), res);
}
{
Solution sln;
s = "bbaac", t = "aba";
auto res = sln.minWindow(s, t);
Assert(std::string("baa"), res);
}
}
2023年4月版
class Solution { public: string minWindow(string s, string t) { if (s.length() < t.length()) { return “”; } std::unordered_map
}
return (-1==iRetIndex)? "" : s.substr(iRetIndex,iRetLen);
}
void DelOrAdd(std::unordered_map
{
auto it = del.find(ch);
if (del.end() == it)
{
more[ch]++;
}
else if (it->second > 1)
{
del[ch]--;
}
else
{
del.erase(ch);
}
}
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++ 实现。
精彩链接
您阅读本篇文章共花了：
发表评论