手表网站欧米茄官网,青岛找网站建设公司,如何做网站挣钱,网站开发盈利模式作者推荐
map|动态规划|单调栈|LeetCode975:奇偶跳
涉及知识点
单调栈
题目
给你一个字符串 s #xff0c;一个整数 k #xff0c;一个字母 letter 以及另一个整数 repetition 。 返回 s 中长度为 k 且 字典序最小 的子序列#xff0c;该子序列同时应满足字母 letter 出…作者推荐
map|动态规划|单调栈|LeetCode975:奇偶跳
涉及知识点
单调栈
题目
给你一个字符串 s 一个整数 k 一个字母 letter 以及另一个整数 repetition 。 返回 s 中长度为 k 且 字典序最小 的子序列该子序列同时应满足字母 letter 出现 至少 repetition 次。生成的测试用例满足 letter 在 s 中出现 至少 repetition 次。 子序列 是由原字符串删除一些或不删除字符且不改变剩余字符顺序得到的剩余字符串。 字符串 a 字典序比字符串 b 小的定义为在 a 和 b 出现不同字符的第一个位置上字符串 a 的字符在字母表中的顺序早于字符串 b 的字符。 示例 1 输入s “leet”, k 3, letter “e”, repetition 1 输出“eet” 解释存在 4 个长度为 3 且满足字母 ‘e’ 出现至少 1 次的子序列
“lee”“leet”“let”“leet”“let”“leet”“eet”“leet” 其中字典序最小的子序列是 “eet” 。 示例 2 输入s “leetcode”, k 4, letter “e”, repetition 2 输出“ecde” 解释“ecde” 是长度为 4 且满足字母 “e” 出现至少 2 次的字典序最小的子序列。 示例 3 输入s “bb”, k 2, letter “b”, repetition 2 输出“bb” 解释“bb” 是唯一一个长度为 2 且满足字母 “b” 出现至少 2 次的子序列。 参数范围 1 repetition k s.length 5 * 104 s 由小写英文字母组成 letter 是一个小写英文字母在 s 中至少出现 repetition 次
单调栈
最简单的情况不限制长度和重复字符
从左到右将s[i]放到栈中放入之前向将栈中大于s[i]的出栈。下面来证明 假定s的最小子系列的为依次为{i1,i2,i3…}。 规则一i1之前没有数小于等于它。否则将此数的放在最前会变得最小。 规则二i1之后没有数小于它否则替换i1会变得更小。 规则三i1和i2之间没有数小于等于i2。 规则四i2之后没有数小于它否则替换i2会变得更小。 … 栈底到栈顶就是最小子系列。 i1在栈底说明它前面的数都大于它所以出栈了。 i1没有出栈说明i1之后没有数比它小否则i1出栈了。 i2之前i1之后没有数据说明两者之间没有数小于等于i2否则不会出栈。 i2没有出栈说明之后没有数据小于它否则出栈了。 …
大数出栈后变成前面的数小后面的数大。也就是递增的单调栈。
注意: {1,1,1} 前面增加1变成{1,1,1,1} 有些规则可能变小有些规则可能变大。
限制长度k
限制了长度也就限制了出栈次数。前面的数变小比后面的数变小更小所以把出栈的机会留给前面。 出栈的时候增加判断如果出栈后使得长度一定少于k则不出栈。 入栈的时候增加判断如果长度已经为k则不入栈。
必须特定个特定字母
如果出栈会造成特定字母不足则不出栈。 入栈时增加处理如果长度为k但当前是特定字母不入栈则特定字母不足出栈栈顶所有特定字母直到非特定字母。出栈它把出栈的特定字母和当前字母入栈。这个操作在超时的边缘。
代码
核心代码
class Solution {
public:string smallestSubsequence(const string s, const int k, const char letter, const int repetition) {int iCanOutCount std::count(s.begin(), s.end(), letter) - repetition;//可以不使用letter的数量vectorchar sta;for (int i 0; i s.length(); i){const auto ch s[i];auto NeedPop [](){if (sta.empty() || (sta.size() s.length() - i k) || (sta.back() ch)){return false;}if ((sta.back() letter) (iCanOutCount 0)){return false;}return true;};while (NeedPop()){iCanOutCount - (sta.back() letter);sta.pop_back();}if (sta.size() k){sta.emplace_back(ch);}else if ((letter ch)( iCanOutCount 0 )){int iCnt 1;while (sta.size() iCnt k ){if (letter sta.back()){iCnt;}sta.pop_back();}while (iCnt--){sta.emplace_back(letter);}}else{iCanOutCount - (letter ch);}}sta.emplace_back(0);return sta.data();}
};测试用例
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 s;int k;char letter;int repetition;{Solution slu;s leet, k 3, letter e, repetition 1;auto res slu.smallestSubsequence(s, k, letter, repetition);Assert(std::string(eet), res);}{Solution slu;s leetcode, k 4, letter e, repetition 2;auto res slu.smallestSubsequence(s, k, letter, repetition);Assert(std::string(ecde), res);}{Solution slu;s bb, k 2, letter b, repetition 2;auto res slu.smallestSubsequence(s, k, letter, repetition);Assert(std::string(bb), res);}{Solution slu;s aaabbbcccddd, k 3, letter b, repetition 2;auto res slu.smallestSubsequence(s, k, letter, repetition);Assert(std::string(abb), res);}{Solution slu;s hjjhhhmhhwhz, k 6, letter h, repetition 5;auto res slu.smallestSubsequence(s, k, letter, repetition);Assert(std::string(hhhhhh), res);}//CConsole::Out(res);
}
优化
非特定字母最多入栈k - repetition。注意 非特定字母入栈的时候也要判断栈的长度小于k。
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 s;int k;char letter;int repetition;{Solution slu;s leet, k 3, letter e, repetition 1;auto res slu.smallestSubsequence(s, k, letter, repetition);Assert(std::string(eet), res);}{Solution slu;s leetcode, k 4, letter e, repetition 2;auto res slu.smallestSubsequence(s, k, letter, repetition);Assert(std::string(ecde), res);}{Solution slu;s bb, k 2, letter b, repetition 2;auto res slu.smallestSubsequence(s, k, letter, repetition);Assert(std::string(bb), res);}{Solution slu;s aaabbbcccddd, k 3, letter b, repetition 2;auto res slu.smallestSubsequence(s, k, letter, repetition);Assert(std::string(abb), res);}{Solution slu;s hjjhhhmhhwhz, k 6, letter h, repetition 5;auto res slu.smallestSubsequence(s, k, letter, repetition);Assert(std::string(hhhhhh), res);}//CConsole::Out(res);
}
2023年3月旧版
class Solution { public: string smallestSubsequence(string s, int k, const char letter, int repetition) { m_c s.length(); int iCanNotUseLetterNum -repetition;//可以不使用letter多少次 int iCanNotUseChar m_c - k; vector vAns; for (const auto ch : s) { if (ch letter) { iCanNotUseLetterNum; } } for (int i 0; i m_c; i) { const auto ch s[i]; while (vAns.size() (ch vAns.back()) iCanNotUseChar ((letter ! vAns.back()) || iCanNotUseLetterNum)) { if (letter vAns.back()) { iCanNotUseLetterNum–; } iCanNotUseChar–; vAns.pop_back(); } vAns.push_back(ch); } string strRet; for (int iIndex vAns.size() - 1; iIndex 0; iIndex–) { const char ch vAns[iIndex]; if (0 iCanNotUseChar) { strRet ch; continue; } if (letter ch ) { if (iCanNotUseLetterNum) { iCanNotUseLetterNum–; iCanNotUseChar–; } else { strRet ch; } } else { iCanNotUseChar–; } } vector tmp(strRet.rbegin(), strRet.rend()); tmp.push_back(0); return tmp.data(); } int m_c; };
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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 实现。
