地产集团网站建设房产网站排名

地产集团网站建设,房产网站排名,wordpress文章自动生成标签,如何自己做免费网站引言 对于编程初学者来说#xff0c;“最小覆盖子串”#xff08;LeetCode 76题#xff09;是理解滑动窗口思想的绝佳案例。这道题看似复杂#xff0c;但只要拆解清楚每一步逻辑#xff0c;就能从“看不懂”到“能手写”。本文会用最通俗的语言、最细致的步骤#xff0c;…引言对于编程初学者来说“最小覆盖子串”LeetCode 76题是理解滑动窗口思想的绝佳案例。这道题看似复杂但只要拆解清楚每一步逻辑就能从“看不懂”到“能手写”。本文会用最通俗的语言、最细致的步骤结合完整代码和流程图带你吃透这道经典题。题目链接【点击进入】引言目录一、先把题目说清楚题目要求关键注意点新手容易踩坑二、为什么不用暴力解法三、滑动窗口核心思想四、代码逐行拆解新手友好版模块1统计t的字符信息模块2初始化窗口变量模块3滑动窗口核心循环关键步骤拆解用例子说话模块4返回结果收尾五、新手常见问题解答问题1为什么count统计的是“达标字符的种类数”而不是总字符数问题2缩小窗口时为什么先left再改hash2问题3如果t里有重复字符比如tAA代码能处理吗六、新手练习建议七、总结目录一、先把题目说清楚题目要求给你两个字符串s和t请在s中找出包含t所有字符的最短连续子串如果s中不存在这样的子串返回空字符串。关键注意点新手容易踩坑子串是s中连续的一段不是随便挑几个字符凑一起t中的字符可能重复比如t aa那么子串里必须至少有两个a要找最短的那个子串没有就返回空。举个例子输入s ADOBECODEBANCt ABC输出BANC包含A、B、C且是最短的二、为什么不用暴力解法新手可能会想把s的所有子串列出来挨个检查是否包含t的所有字符再挑最短的。但这种方法有致命问题s长度为m时子串数量是m*(m1)/2时间复杂度是O(m²)如果m是 10^5计算量会达到 10^10直接超时。而滑动窗口算法能把时间复杂度降到O(m n)n是t的长度效率提升百倍这也是这道题的核心解法。三、滑动窗口核心思想想象你手里有一个可伸缩的“窗口”比如纸条圈在s这个长字符串上从左到右滑扩大窗口先把窗口右边拉大直到窗口里包含t的所有字符缩小窗口再把窗口左边收紧在“窗口仍包含t所有字符”的前提下缩到最短滑动重复继续往右滑窗口重复“扩大-缩小”直到滑到s末尾。整个过程就像“找东西”先圈出一个包含目标的范围再把范围缩到最小既不丢东西又最省空间。四、代码逐行拆解新手友好版先贴完整代码和题目一致再拆成“小模块”讲解每个模块只解决一个小问题classSolution{public:stringminWindow(string s,string t){// 模块1统计t的字符信息inthash1[128]{0};// 存t中每个字符的出现次数ASCII码对应索引intkinds0;// t中有多少种不同的字符比如tABCkinds3for(autoch:t){if(hash1[ch]0){// 第一次遇到这个字符时kinds1kinds;}}// 模块2初始化窗口相关变量inthash2[128]{0};// 存当前窗口中每个字符的出现次数intminlenINT_MAX;// 记录最小窗口长度初始值设为最大整数intbegin-1;// 记录最小窗口的起始位置初始为-1表示没找到// 模块3滑动窗口核心循环双指针left/rightfor(intleft0,right0,count0;rights.size();right){// 步骤1扩大窗口——把right指向的字符加入窗口charins[right];hash2[in];// 窗口中该字符数量1// 如果窗口中该字符数量刚好等于t中的数量说明这个字符“达标”了if(hash2[in]hash1[in]){count;// 达标字符的种类数1}// 步骤2缩小窗口——当所有字符都达标时尝试缩到最短while(countkinds){// 步骤2.1更新最小窗口信息intcurrent_lenright-left1;// 当前窗口长度if(current_lenminlen){minlencurrent_len;// 更新最小长度beginleft;// 更新最小窗口起始位置}// 步骤2.2把left指向的字符移出窗口charouts[left];left;// left指针右移窗口左边界缩小// 如果移出后该字符数量低于t的要求说明这个字符“不达标”了if(hash2[out]hash1[out]){count--;// 达标字符的种类数-1}hash2[out]--;// 窗口中该字符数量-1}}// 模块4返回结果if(begin-1){// 没找到符合条件的窗口return;}else{// 从begin开始截取长度为minlen的子串returns.substr(begin,minlen);}}};模块1统计t的字符信息新手提问为什么用数组hash1而不是列表/字典答因为字符的ASCII码范围是0-127比如’A’65‘B’66用长度为128的数组索引直接对应字符的ASCII码访问速度是O(1)比字典哈希表更快代码也更简单。举个例子如果t ABC遍历后hash1[A] 1A’在t中出现1次hash1[B] 1hash1[C] 1kinds 3t中有3种不同字符模块2初始化窗口变量hash2和hash1对应专门统计当前窗口里的字符数量minlen初始值设为INT_MAXC里的最大整数这样第一次找到有效窗口时肯定能更新begin初始为-1用来标记最小窗口的起始位置最后如果还是-1说明没找到有效窗口。模块3滑动窗口核心循环这里用了双指针right右指针负责扩大窗口、left左指针负责缩小窗口还有一个关键变量count记录“窗口中达标字符的种类数”。关键步骤拆解用例子说话还是用s ADOBECODEBANCt ABC举例扩大窗口right从0开始右移依次加入’A’、‘D’、‘O’、‘B’、‘E’、‘C’。当加入’C’时hash2[A]1、hash2[B]1、hash2[C]1count3等于kinds3此时窗口是ADOBECleft0right5。缩小窗口先算当前窗口长度5-016minlen更新为6begin0移出left0的’A’hash2[A]变成0count减到2退出缩小循环right继续右移直到再次让count3重复缩小步骤。最终结果当right移到13字符’C’时窗口是BANCleft9right12长度4这是最小的所以begin9minlen4。模块4返回结果收尾如果begin-1说明全程没找到有效窗口返回空否则用substr(begin, minlen)截取子串就是答案。五、新手常见问题解答问题1为什么count统计的是“达标字符的种类数”而不是总字符数答比如tAABkinds2A和B。如果窗口里有2个A和1个Bcount2A和B都达标此时窗口有效如果统计总字符数会分不清“数量是否够”比如1个A和1个B总字符数是2但A不达标。问题2缩小窗口时为什么先left再改hash2答out s[left]先记录要移出的字符然后left移动指针最后hash2[out]--减少该字符的计数逻辑上是“先标记要移出的字符→移动指针→更新计数”顺序不能乱。问题3如果t里有重复字符比如tAA代码能处理吗答能比如tAAhash1[A]2kinds1。只有当窗口里hash2[A]2时count1才会进入缩小窗口步骤保证窗口里至少有2个A。六、新手练习建议手动走一遍例子拿sADOBECODEBANCtABC把每个步骤的left、right、count、hash2的值写下来理解窗口的变化修改测试用例比如tAAsAAsABAACBAA跑一遍代码看结果是否正确替换数据结构把数组hash1/hash2换成unordered_map改写代码对比两种方式的区别同类题拓展做完这道题再做“找到字符串中所有字母异位词”LeetCode 438、“无重复字符的最长子串”LeetCode 3巩固滑动窗口思想。七、总结滑动窗口解最小覆盖子串的核心就3点统计目标先算清楚t的字符种类和数量双指针控窗口right扩、left缩一扩一缩找最短有效窗口count做标志用count判断窗口是否有效避免重复检查。对于编程初学者来说不用一开始追求“最优解”先理解每一步的逻辑手动模拟执行过程再慢慢优化。滑动窗口是算法里的高频考点掌握这道题相当于掌握了一大类字符串问题的解法