网站弹窗特效,企业服务平台公众号,成都做小程序,新国标小区网络建设76. 最小覆盖子串
总结和复盘
这是时隔1年4个月之后#xff0c;再次写的题解#xff0c;比第一次要清晰很多。 我刚开始#xff0c;就是用方法一做的#xff0c;提交之后报超出内存限制#xff1b; 对方法一进行优化#xff0c;得到方法二#xff0c;提交之后就AC了。…76. 最小覆盖子串
总结和复盘
这是时隔1年4个月之后再次写的题解比第一次要清晰很多。 我刚开始就是用方法一做的提交之后报超出内存限制 对方法一进行优化得到方法二提交之后就AC了。 这是第二次做这道题 第一次的题解是写给自己看的有很多思考的过程作为题解是不清晰的。 这一次的题解会更好理解。 首先我新增了两个成员函数相当于把功能拆分开了这样更容易我们去理解 其次由于使用了其他函数于是我把过程之中用到的变量提到了类中做成了成员变量这样我就方便在其他成员函数之中使用。 先做再优化。
解法一
// 解法一 //
// 由于使用substr从s之中截取子字符串并保存在answer之中导致内存超出了限制class Solution {
public:string answer; // 这道题的答案由于保存了结果字符串导致内存超出了限制unordered_mapchar, int window; // 这就是滑动的窗口unordered_mapchar, int need; // 目标字符串 t 中每个字符的情况int left 0, right 0; // 用于滑动的指针int validCount 0; // 「与字符串t中数量相等的字符」的数量string minWindow(string s, string t) {// 初始化 needfor (char c : t)need[c];// 核心思想: 不断增大right找到一个可行解;while (right s.length()) {char R s[right];// 先看这第一步R 是我们需要的字符时if (need.count(R) 1) { window[R]; // 要放到窗口之中if (window[R] need[R]) { // 该字符的数量已经达到要求validCount; // 已就绪的字符数量1if (validCount need.size()) { // 如果所有字符都就绪更新一下answerupdateAnswer(s);}}}// 最后看这第三步// 你想啊如果只是rightleft不动那这个窗口岂不是越来越长了// 所以要考虑一下什么时候left也要// 核心思想当前的窗口中已经包含了不止一个解的时候我们让left去优化一下// 因为题目要求找字符串s的最小字串// 比如sA-B-C---BAC--, tABC// 不断的增加right指针当这个窗口达到「A-B-C---BAC」时// 这也是s的字串 且 也涵盖t中的所有字符// 但这不是最优解// 所以要增加left让窗口变成「BAC」// 才是最优解moveLeftFindThePerfectAnswer(s, t);// 再看这第二步R 不是我们需要的字符则 right 继续寻找right;}return answer;}void moveLeftFindThePerfectAnswer(const string s, const string t) {while (validCount need.size()) { // 已经找到解的情况之下才会优化解char L s[left];if (need.count(L) 1) { // 字符L是目标的其中一个字符时代表可能可以优化updateAnswer(s);window[L]--;if (window[L] need[L])validCount--;if (window[L] 0)window.erase(L);}// 不管是否优化了left都要增加。但至少要让窗口中保留一个有用的解也就是while的条件left;}}void updateAnswer(const string s) {string tmp_answer s.substr(left, right - left 1);if (answer.empty()) { // 首次情况下answer tmp_answer;} else if (tmp_answer.length() answer.length()) { // 找到了更优化解的情况answer tmp_answer;}}
};解法二
// 解法二 //
// 优化answer的计算不使用substr
// 因为答案是一个子串是连续的
// 所以使用start和len来保存即可
// 到最后一刻才使用substr从s之中截取子串出来class Solution {
public:struct MyAnswer {int start INT_MAX;int len INT_MAX;};MyAnswer answer; // 这道题的答案unordered_mapchar, int window; // 这就是滑动的窗口unordered_mapchar, int need; // 目标字符串 t 中每个字符的情况int left 0, right 0; // 用于滑动的指针int validCount 0; // 「与字符串t中数量相等的字符」的数量string minWindow(string s, string t) {// 初始化 needfor (char c : t)need[c];// 核心思想: 不断增大right找到一个可行解;while (right s.length()) {char R s[right];// 先看这第一步R 是我们需要的字符时if (need.count(R) 1) { window[R]; // 放到窗口之中if (window[R] need[R]) { // 该字符的数量已经达到要求validCount; // 已就绪的字符数量1if (validCount need.size()) { // 如果所有字符都就绪更新一下answerupdateAnswer(s);}}}// 最后看这第三步// 你想啊如果只是rightleft不动那这个窗口岂不是越来越长了// 所以要考虑一下什么时候left也要// 核心思想当前的窗口中已经包含了不止一个解的时候我们让left去优化一下// 因为题目要求找字符串s的最小字串// 比如sA-B-C---BAC--, tABC// 不断的增加right指针当这个窗口达到「A-B-C---BAC」时// 这也是s的字串 且 也涵盖t中的所有字符// 但这不是最优解// 所以要增加left让窗口变成「BAC」// 才是最优解moveLeftFindThePerfectAnswer(s, t);// 再看这第二步R 不是我们需要的字符则 right 继续寻找right;}// 要考虑没有找到解的情况返回空字符串return (answer.start INT_MAX answer.len INT_MAX)? : s.substr(answer.start, answer.len);}void moveLeftFindThePerfectAnswer(const string s, const string t) {while (validCount need.size()) { // 已经找到解的情况之下才会优化解char L s[left];if (need.count(L) 1) { // 字符L是目标的其中一个字符时代表可能可以优化updateAnswer(s);window[L]--;if (window[L] need[L])validCount--;if (window[L] 0)window.erase(L);}// 不管是否优化了left都要增加。但至少要让窗口中保留一个有用的解也就是while的条件left;}}void updateAnswer(const string s) {int new_length right - left 1;if (answer.start INT_MAX answer.len INT_MAX) { // 首次情况下answer.start left;answer.len new_length;} else if (new_length answer.len) { // 找到了更优化解的情况answer.start left;answer.len new_length;}}
};作者坤坤学编程 链接时隔1年4个月之后再次写的题解比第一次要清晰很多。 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
