您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

Leetcode每日刷题【难】--Day 19

76. 最小覆盖子串

终于想出来了,看着C++题解,其++变量实数不可忽视。被坑了几个小时

这道题的使用到的是双指针的知识点。

具体要用到滑动窗口,这个在条件判断的时候会比较麻烦~

  • 具体解析:先记录一下目标中的字符种类及其个数
    再利用双指针逐个遍历字符串s
    过程中要2个步骤:
    **1.先要找到一个区间:区间里边要有目标字符(包含种类和个数要求) **

    2.进行滑动:这里分两个条件,①先滑动左边界,找到尽可能小的区间和起点;②如果不满足第一个条件,则进行右边界扩大,达到步骤1之后就进行步骤2.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        flag = Counter(t)
        tnum, left, cnt, minlength,minl = len(t), 0, 0, len(s)+1, 0
        for right, i in enumerate(s):
            if i in flag.keys():
                # 这是为了保证每个窗口能有足够的t中的字母,每算入一个,就减少一个等待算入的值
                flag[i] -= 1  # 减少一个等待计入的
                if flag[i] >= 0:
                    cnt += 1  # 计算计入的要求的字母长度
                
                while cnt == tnum:  # 如果足够了,所需的和计入的一致多
                    if right - left + 1 < minlength:  # 该窗口小于  比较小的窗口
                        minl = left  # 记录起始位置
                        minlength = right - left + 1  # 记录区间长度
                    if s[left] in flag.keys():
                        flag[s[left]] += 1  # 退出一个计入的数(为了接下来能够进行计入)
                        # 左边界往右试探  (保证大于0的原因是,在遍历s过程中,会出现多个相同的字符,这些是我们不需要的,不能因为他们的离开界限而使得要求的字符的个数变化)
                        """
                        上面这么长的话是什么意思呢?
                        比如说我们需要 t = 'AB',s = 'BBBBBBBBBBAAAAA'
                        在第一个B到第一个A之间,能够开始进行这个循环,每一个s[left]都存在,如果不加下面这个						判断会使得,cnt不分条件--,left没办法尽可能快地在有边界行动之前达到最后一个b。
                        简单来说:上边cnt+=1是在需要多少个字母加多少个字母的条件下进行地,相应地减也应该如此
                        """
                        if flag[s[left]] > 0:  
                            cnt -= 1  # 长度减一
                    left += 1  # 窗口左边界向右移动一格
        return s[minl: minlength+minl] if minlength <= len(s) else ''

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进