当前位置: 首页 > article >正文

力扣017_最小覆盖字串题解----C++

题目描述

  1. 我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针,一个用于「延伸」现有窗口的 r 指针,和一个用于「收缩」窗口的 l 指针。在任意时刻,只有一个指针运动,而另一个保持静止。我们在 s 上滑动窗口,通过移动 r 指针不断扩张窗口。当窗口包含 t 全部所需的字符后,如果能收缩,我们就收缩窗口直到得到最小窗口。、
  2. 如何判断当前的窗口包含所有 t 所需的字符呢?我们可以用一个哈希表表示 t 中所有的字符以及它们的个数,用一个哈希表动态维护窗口中所有的字符以及它们的个数,如果这个动态表中包含 t 的哈希表中的所有字符,并且对应的个数都大于或等于t 的哈希表中各个字符的个数,那么当前的窗口是「可行」的。

假设这是我们对应的是s和t

创建unordered_map<char,int> hs,ht

我们定义两个指针,作为遍历s的窗口,再定义一个cnt作为窗口内的有效字符。

遍历s,用for循环,每循环一次r,把r指向的值存入到hs中,

 unordered_map<char,int> hs,ht;
        string ans;
        for(auto &c:t) ht[c]++; 
        int l=0,r=0,cnt=0; //l为窗口的左边界,r为窗口的右边界
        for(;r<s.size();r++){ //每次循环右边界右移一次
            hs[s[r]]++;

此时有两种情况,当hs[s[r]]<=ht[s[r]] ,cnt++。

如果hs[s[l]]>ht[s[l]],说明hs里面已经存在两个相同的有效值了,如下图

ht:ABA,cnt=2 因为我们要找的是最小覆盖字串,且包含了A有效字符,所有这个时候我们的左窗口右移,并且减去一个A 

while(hs[s[l]]>ht[s[l]]){ //这个语句会右移左边界,比如这个边界字符不在t里,
                hs[s[l]]--;           //或者符合条件的边界值在后面又增加了一个且和左边界值相同,那么就可以右移左边界
                l++;

一次次的循环如下 

当我们的cnt 有效字符等于t.size()的时候,也就是这个窗口包含了t字符串的所有。

 if(cnt==t.size()){ //有效字符等于字符串t的长度,我们可以放入答案;
                if(ans.empty()||r-l+1<ans.size()) ans=s.substr(l,r-l+1);或者对比前窗口的大小和当前的大小,然后决定是否更新ans。
            }

如下即为全部的代码

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int> hs,ht;
        string ans;
        for(auto &c:t) ht[c]++; 
        int l=0,r=0,cnt=0; //l为窗口的左边界,r为窗口的右边界
        for(;r<s.size();r++){ //每次循环右边界右移一次
            hs[s[r]]++;
            if(hs[s[r]]<=ht[s[r]]) cnt++; //在找到第一个符合条件的窗口后,这个语句不会再运行了。
                                          //ps.该语句的作用是统计窗口内的有效字符
            //左边界右移                              
            while(hs[s[l]]>ht[s[l]]){ //这个语句会右移左边界,比如这个边界字符不在t里,
                hs[s[l]]--;           //或者符合条件的边界值在后面又增加了一个且和左边界值相同,那么就可以右移左边界
                l++;
            }
            if(cnt==t.size()){ //有效字符等于字符串t的长度,我们可以放入答案;或者对比前窗口的大小和当前的大小,然后决定是否更新ans。
               if(ans.empty()||r-l+1<ans.size()) ans=s.substr(l,r-l+1); 对比前窗口的大小和当前的大小,然后决定是否更新ans。
            }
        }
        return ans;
    }
};

原文地址:https://blog.csdn.net/puppy_1mo/article/details/145400199
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/527427.html

相关文章:

  • AI学习指南HuggingFace篇-Datasets 库入门
  • [EAI-028] Diffusion-VLA,能够进行多模态推理和机器人动作预测的VLA模型
  • 研发的护城河到底是什么?
  • 双指针c++
  • 5.4.1 结构化分析方法
  • Golang 并发机制-3:通道(channels)机制详解
  • 【C/C++】区分0、NULL和nullptr
  • 26.Word:创新产品展示说明会【9】
  • Keepalived 安装
  • 基于微信小程序的实习记录系统设计与实现(LW+源码+讲解)
  • DeepSeek的崛起与OpenAI的守擂:AI大模型时代的竞争新格局
  • 自动化数据备份与恢复:让数据安全无忧
  • 动态规划 (环形)
  • Spring的AOP的JoinPoint和ProceedingJoinPoint
  • 网络编程复习
  • 从0开始,来看看怎么去linux排查Java程序故障
  • Day31-【AI思考】-深度学习方法论全解析——科学提升学习效率的终极指南
  • Synology 群辉NAS安装(7)lsof指令和synogear
  • 半导体SAP管理系统:数字化转型的驱动力
  • ComfyUI使用教程、开发指导、资源下载