【刷题】滑动窗口精通 — Leetcode 30. 串联所有单词的子串 | Leetcode 76. 最小覆盖子串

简介: 经过这两道题目的书写,相信大家一定深刻认识到了滑动窗口的使用方法!!!下面请大家继续刷题吧!!!

送给大家一句话:

充满着欢乐与斗争精神的人们,永远带着欢乐,欢迎雷霆与阳光。 —— 赫胥黎

滑动窗口精通

前言

相信通过前两篇的文章的讲解,大家已经对滑动窗口有了较深的认识,今天我们来挑战一下!!!

来做两道困难级的题目。

Leetcode 30. 串联所有单词的子串

家人们!!!上链接!!!30. 串联所有单词的子串

题目描述

根据题目描述,这道题看起来很是复杂呢!?!?

我们要在一个字符串中寻找包含words的所有单词的子串,并会返回对应的开始位置(开始索引)。看这描述十分类似这道题目 438. 找到字符串中所有字母异位词 ,一个是寻找异位词,一个是寻找"异位单词串"。本质是十分相似的。

来看一个样例:

  • 输入:s = “barfoothefoobarman”, words = [“foo”,“bar”]
  • 输出:[0,9]
  • 解释:因为 words.length == 2 同时 words[i].length == 3,连接的子字符串的长度必须为 6。

子串 “barfoo” 开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。

子串 “foobar” 开始位置是 9。它是 words 中以 [“foo”,“bar”] 顺序排列的连接。

  • 输出顺序无关紧要。返回 [9,0] 也是可以的。

根据这样例,更容易想象为是如同字母一样。

算法思路

我们先把每个单词抽象为一个字母(方便我们梳理思路),我们只需要找到一个子串中有所有的“字母”即可。

那么,我们来看最简单的算法:暴力枚举。就是遍历所有的子串,以样例来说:

  1. bar foo the foo bar man (注意步长是单词的长度),从左到右依次遍历,寻找满足条件的子串。
  2. 我们来思考一下,当该躺不满足条件时:

很明显,无需把right重新移动的到left的位置重新开始,直接继续进行移动就可以。

3.所以此时构成滑动窗口的条件两个指针移动方向一致

那么我们就按照滑动窗口的解题模版来思考细节:

  • 进窗口
  • 判断
  • 出窗口
  • 更新结果(位置待定)

首先我们要解决的是个一般性问题:s 字符串的长度一定是单词的整数倍吗???

显然不是!

那么就要进行多次滑动窗口!保证可以遍历到所有可能的子串。那进行几次呢???

可以看出来只需要进行单词个数次的循环即可!!!再多就发生重复了!

这样大致的框架就有了,剩下的就是然后判断单词是否满足条件。

依旧时候使用哈希算法,利用无向图来模拟哈希表(string 映射 int)。'

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        //预备工作
        //哈希表1
        unordered_map<string,int> hash1;
        for(auto ch : words) hash1[ch] ++; //对words进行处理
        // 基本变量
        int len = words[0].size(); //单词长度(步长) 
        int m = words.size();//单词个数
        int n = s.size();//字符串长度
        //答案
        vector<int> ans;
        //多次进行滑动窗口
        for(int i = 0;i < len;i++)
        {
            //哈希表2 用来进行比较
            unordered_map<string,int> hash2;
            //进窗口 注意一次移动的步长 注意结束条件(保证最后一个是完整单词,不然会发生越界)
            for(int left = i ,right = i ,count = 0; right + len <= n ; right += len )
            {
                string in = s.substr(right,len);
                //进窗口 维护count++ (有效单词数加一)
                if(++hash2[in] <= hash1[in])
                {
                    count++;
                }
                //判断是否超出长度
                if(right - left + 1 > m * len)
                {
                    string out = s.substr(left,len);
                    //出窗口 维护count
                    if(hash2[out]-- <= hash1[out]) count--;
                    left += len;
                }
                //满足条件  更新结果
                if(count == m)
                {
                    ans.push_back(left);
                }
            } 
        }
        return ans;
    }
};

我们提交:过啦!!!!

Leetcode 76. 最小覆盖子串

家人们!!! 上链接!!!76. 最小覆盖子串

题目描述

根据题目描述,我们需要再字符串中寻找能够覆盖 t 中所有字符的 最短子串,这个“覆盖”是包含 t 中的每个字母,不用管顺序。来看样例:

  • 输入:s = “ADOBECODEBANC”, t = “ABC”
  • 输出:“BANC”
  • 解释:最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。

看了样例,应该就理解了这个“覆盖”:

  1. 对应字母个数必须大于等于 t 中字母个数
  2. 可以包含其它字母

算法思路

先来最直接的办法 — 暴力枚举,我们来看暴力算法是如何进行的:

  1. 首先找到一个包含于 t 的字母
  2. 然后从这个位置开始遍历
  3. 直到满足 t 中的每个字母都能在该子串中找到
  4. 然后再找到下一个包含于 t 的字母 重复 1 - 3

这样就完成了任务,那么如何进行优化呢???

根据暴力的步骤,我们可以看出来两个指针的移动方向是一致的,所以就可以进行滑动窗口算法了。

那么我们就按照滑动窗口的解题模版来思考细节:

  • 进窗口
  • 判断
  • 出窗口
  • 更新结果(位置待定)

这个判断要怎样进行判断???

肯定是使用哈希算法,但是如何保证对应字母个数必须大于等于 t 中字母个数呢???

这一步与之前的判断略有不同,因为我们可以多字母,来看代码:

class Solution {
public:
    string minWindow(string s, string t) {
    //滑动窗口 + 哈希算法
    
    //准备工作
    int kinds = 0; //字母种类 方便判断
    int hash1[128] = {0}; //哈希表1 因为只有使用数组比较方便
    //遍历所有字母 确定个数
    for (auto ch : t) 
        if (hash1[ch]++ == 0) kinds++;
    // 长度 
    int n = s.size();
    //哈希表2 用来比较
    int hash2[128] = { 0 }; 
    int begin = -1 ,minlen = INT_MAX;
    for(int left = 0,right = 0 ,count = 0;right < n;right++)
    {
        
        char in = s[right];
        //进窗口 维护count (对应字母相等时更新 保证满足条件 有效字母加一)
        if(++hash2[in] == hash1[in]) count++;
        //判断
        while(count == kinds)
        {
            //更新结果
            if(right - left + 1 < minlen)
            {
                minlen = right - left + 1;
                begin = left;
            }
            char out = s[left];
            //出窗口 维护count (相等时出窗口 有效字母减少)
            if(hash2[out]-- == hash1[out]) count--;
            left++;
        }
    }
    return begin == -1 ? "" : s.substr(begin,minlen);
    }
};

提交:过啦!!!!!!

经过这两道题目的书写,相信大家一定深刻认识到了滑动窗口的使用方法!!!

下面请大家继续刷题吧!!!

Thanks♪(・ω・)ノ 谢谢阅读!!!

下一篇文章见!!!

相关文章
|
10天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
10天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
11天前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
11天前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
11天前
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
|
11天前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
11天前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
11天前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
11天前
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
|
11天前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串