【算法】基础算法002之滑动窗口(二)

这篇具有很好参考价值的文章主要介绍了【算法】基础算法002之滑动窗口(二)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【算法】基础算法002之滑动窗口(二),算法,哈希算法,散列表,算法

👀樊梓慕:个人主页

 🎥个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》

🌝每一个不曾起舞的日子,都是对生命的辜负


目录

前言

 5.水果成篮(medium)

 6.找到字符串中所有字母异位词

7.串联所有单词的子串(hard) 

8.最小覆盖字串(hard)


前言

滑动窗口专题续作,本篇文章继续围绕滑动窗口进行讲解,并辅以实战OJ题帮助理解。


 欢迎大家📂收藏📂以便未来做题时可以快速找到思路,巧妙的方法可以事半功倍。 

=========================================================================文章来源地址https://www.toymoban.com/news/detail-828503.html

GITEE相关代码:🌟樊飞 (fanfei_c) - Gitee.com🌟

=========================================================================


 5.水果成篮(medium)

904. 水果成篮 - 力扣(LeetCode)https://leetcode.cn/problems/fruit-into-baskets/description/

你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:

  • 你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
  • 你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
  • 一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。

给你一个整数数组 fruits ,返回你可以收集的水果的 最大 数目。

【算法】基础算法002之滑动窗口(二),算法,哈希算法,散列表,算法​ 阅读题目,其实就是找出一个最长的子数组的长度,要求子数组中不能超过两种元素。

思路:

  • 如果大小超过2:说明窗口内水果种类超过了两种。那么就从左侧开始依次将水果划出窗口,直到哈希表的大小小于等于2,然后更新结果;
  • 如果没有超过2:说明当前窗口内水果的种类不超过两种,直接更新结果ret。
     

 有了思路,画图独立完成代码,不要直接看博主的代码。

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int> hash;
        int left = 0, right = 0;
        int ret = 0;
        int n = fruits.size();
        while (right < n)
        {
            hash[fruits[right]]++;//进入窗口
            while (hash.size() > 2)//判断
            {
                hash[fruits[left]]--;//离开窗口
                if (hash[fruits[left]] == 0)
                {
                    hash.erase(fruits[left]);
                }
                left++;
            }
            ret = max(ret, right - left + 1);//更新结果
            right++;
        }
        return ret;
    }
};

但如果使用容器,我们需要频繁地erase元素,这就牺牲了一定的时间。

【算法】基础算法002之滑动窗口(二),算法,哈希算法,散列表,算法

又因为题目说明元素个数是有限的:

【算法】基础算法002之滑动窗口(二),算法,哈希算法,散列表,算法

​所以我们可以利用数组模拟一个哈希表,这样效率会显著提升。 

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int hash[100001]={0};
        int left=0,right=0,kinds=0;
        int ret=0;
        int n=fruits.size();
        while(right<n)
        {
            if(hash[fruits[right]]==0) kinds++;
            hash[fruits[right]]++;//进入窗口
            while(kinds>2)//判断
            {
                hash[fruits[left]]--;//离开窗口
                if(hash[fruits[left]]==0)
                    kinds--;
                left++;
            }
            ret=max(ret,right-left+1);//更新结果
            right++;
        }
        return ret;
    }
};

【算法】基础算法002之滑动窗口(二),算法,哈希算法,散列表,算法


 6.找到字符串中所有字母异位词

438. 找到字符串中所有字母异位词 - 力扣(LeetCode)https://leetcode.cn/problems/find-all-anagrams-in-a-string/

给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。

【算法】基础算法002之滑动窗口(二),算法,哈希算法,散列表,算法

不难发现,我们需要在字符串 s 中维护一个滑动窗口,且该滑动窗口的长度始终与字符串 p 相等。

然后依据该窗口内的元素构建哈希表与字符串 p 的哈希表作比较,如果两个哈希表相同,那么就证明滑动窗口内为字符串 p 的异位词。

那么如何比较两个哈希表是否相同呢?如题意:

【算法】基础算法002之滑动窗口(二),算法,哈希算法,散列表,算法

​字符串 s 和 p 仅包含小写字母,所以我们只要遍历即可,时间复杂度为常数级,可以忽略。 

有了思路,画图独立完成代码,不要直接看博主的代码。 

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hash1[26] = { 0 };
        for (auto e : p)
            hash1[e - 'a']++;
        int hash2[26] = { 0 };
        int left = 0, right = 0;
        int np = p.size();
        int ns = s.size();
        vector<int> ret;
        while (right < ns)
        {
            hash2[s[right] - 'a']++;//进入窗口
            if (right - left + 1 > np)//判断
                hash2[s[left++] - 'a']--;//离开窗口
            int flag = 0;
            for (int i = 0; i < 26; i++)
                if (hash1[i] != hash2[i])
                    flag = 1;
            if (flag == 0)
                ret.push_back(left);//更新结果
            right++;
        }
        return ret;
    }
};

可是如果 s 和 p 内不光存储小写字母,或者 s 和 p 是某种容器存储的是字符串,我们又该如何处理呢?如果还按照遍历的方式显然不现实,所以我们需要引入『 有效字符计数器count』。

  • 在每次『 进入窗口』之后,要维护count的值:如果该进入窗口的字符在 s哈希表 中的数目小于或等于 p哈希表 中的数目,那么就证明此时进入窗口的字符是 有效字符,count++;
  • 在每次『 离开窗口』之前,要维护count的值:如果该离开窗口的字符在 s哈希表 中的数目小于或等于 p哈希表 中的数目,那么就证明要离开窗口的字符是 有效字符,count--;
  • 每轮如果 有效字符数目与 p字符串长度相等,那么就证明此时 s字符串窗口内是 p字符串 的异位词,将left尾插到vector中。
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hash1[26] = { 0 };
        for (auto e : p)
            hash1[e - 'a']++;
        int hash2[26] = { 0 };
        int left = 0, right = 0, count = 0;
        int np = p.size();
        int ns = s.size();
        vector<int> ret;
        while (right < ns)
        {
            char in = s[right];
            if (++hash2[in - 'a'] <= hash1[in - 'a']) count++;//进入窗口后维护count
            if (right - left + 1 > np)//判断
            {
                char out = s[left++];
                if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;//离开窗口前维护count
            }
            if (count == np)
                ret.push_back(left);//更新结果
            right++;
        }
        return ret;
    }
};

7.串联所有单词的子串(hard) 

30. 串联所有单词的子串 - 力扣(LeetCode)https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

给定一个字符串 s 和一个字符串数组 words words 中所有字符串 长度相同

 s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

  • 例如,如果 words = ["ab","cd","ef"], 那么 "abcdef", "abefcd""cdabef", "cdefab""efabcd", 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串,因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

【算法】基础算法002之滑动窗口(二),算法,哈希算法,散列表,算法

其实本题就是第6题的升级版,只不过第6题的原子是字符,本题的原子是字符串,因为给定的容器words内存储的字符串都是等长的。

所以整体的思路与第6题是完全相同的,只不过需要处理一些细节。


细节一:

执行一次滑动窗口逻辑不能包括所有情况,因为我们把字符串看作一个原子处理,但是字符串由一个个字符构成,一个字符串内的部分字符可以和另一个字符串的部分字符组成新的字符串,所以我们需要充分考虑所有情况,经过观察发现我们需要执行 字符串原子的长度次len 就能包含所有情况,比如:

【算法】基础算法002之滑动窗口(二),算法,哈希算法,散列表,算法

这反映到left和right开始的位置。 


细节二:

结束条件应为 right + 原子字符串长度len > 字符串长度 。

因为如果大于,right再往后就够不成原子字符串了。


 细节三:

right 与 left 每次移动 原子字符串长度len,而不是1。


细节四:

『 判断』条件应为 right - left + 1 > 原子字符串长度len *  words中的字符串个数。

【算法】基础算法002之滑动窗口(二),算法,哈希算法,散列表,算法


有了思路,画图独立完成代码,不要直接看博主的代码。 

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string,int> hash1;
        for(auto& e: words)
            hash1[e]++;
        
        int ns=s.size();
        int nw=words.size();
        int len=words[0].size();
        vector<int> ret;
        for(int i=0;i<len;i++)//细节1
        {
            int left=i,right=i,count=0;
            unordered_map<string,int> hash2;//维护窗口内单词的频次
            while(right + len <= ns)//细节2
            {
                //进入窗口+维护count
                string in = s.substr(right,len);
                hash2[in]++;
                if(hash2[in]<=hash1[in]) count++;

                //判断
                if(right-left+1 > len*nw) //细节4
                {
                    //离开窗口+维护count
                    string out=s.substr(left,len);
                    if(hash2[out]<=hash1[out]) count--;
                    hash2[out]--;
                    left+=len;//细节3
                }

                if(count==nw)
                {
                    ret.push_back(left);//更新结果
                }
                right+=len;//细节3
            }
        }
        return ret;
    }
};

到这代码还能进一步优化。


细节五:

维护count时,因为判断语句会被执行,所以如果进入窗口的字符串in在hash1中不存在,那么in这个字符串就会加入到hash1中,这无疑是一种浪费,所以在比较之前,我们可以判断一下in是否在hash1中,如果不在那也就没有比较的必要了,out那块同理。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string,int> hash1;
        for(auto& e: words)
            hash1[e]++;
        
        int ns=s.size();
        int nw=words.size();
        int len=words[0].size();
        vector<int> ret;
        for(int i=0;i<len;i++)//细节1
        {
            int left=i,right=i,count=0;
            unordered_map<string,int> hash2;//维护窗口内单词的频次
            while(right + len <= ns)//细节2
            {
                //进入窗口+维护count
                string in = s.substr(right,len);
                hash2[in]++;
                if(hash1.count(in) && hash2[in]<=hash1[in]) count++;//细节5

                //判断
                if(right-left+1 > len*nw) //细节4
                {
                    //离开窗口+维护count
                    string out=s.substr(left,len);
                    if(hash1.count(out) && hash2[out]<=hash1[out]) count--;//细节5
                    hash2[out]--;
                    left+=len;//细节3
                }

                if(count==nw)
                {
                    ret.push_back(left);//更新结果
                }
                right+=len;//细节3
            }
        }
        return ret;
    }
};

8.最小覆盖字串(hard)

76. 最小覆盖子串 - 力扣(LeetCode)https://leetcode.cn/problems/minimum-window-substring/description/

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。

注意:

  • 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串,我们保证它是唯一的答案。

【算法】基础算法002之滑动窗口(二),算法,哈希算法,散列表,算法

 同样的我们最先想到暴力枚举+哈希表的办法,但我们可以观察得到一定的规律做优化。


第一个问题:

当right右移到满足覆盖的条件时,left左移,right是否需要回退呢?

其实不需要,因为中间的元素我们是知道的,只需要在left左移时判断right是否需要移动即可。

  • 当left右移后,如果窗口内还满足覆盖条件,那么就证明right此时可以不动;
  • 当left右移后,如果窗口内不满足覆盖条件,那么就证明right要右移寻找新的满足条件的字符。

 而且根究上面的进出窗口,我们可以知道出窗口之前,即left右移之前,此时窗口内是满足条件的字符串,所以『 更新结果』要在『 离开窗口』之前完成。

并且如果窗口内一直满足覆盖条件,那么就应该一直出窗口,直到不满足覆盖条件为止,所以这里应该用while。


第二个问题:

如何判断是否满足覆盖条件,我们之前说利用哈希表,但两个哈希表又如何判断相等呢?

之前的题目相信对你有所启发,我们是利用了一个 有效字符计数器count 来判断,在这里我们同样可以利用这个 count,但唯一不同的是,此 count 要统计的是字符种类,而不是字符数,因为题目说了,对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

所以进入窗口之后维护count的条件,应该是哈希表中对应字符的个数相等,此时才证明恰好覆盖。


 有了思路,画图独立完成代码,不要直接看博主的代码。 

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128]={0};
        int kinds=0;
        for(auto ch : t)
        {
            if(hash1[ch]==0)//统计有效字符有多少种
                kinds++;
            hash1[ch]++;
        }

        int left=0,right=0,count=0;
        int ns=s.size();
        int nt=t.size();
        int hash2[128]={0};

        int minLen=INT_MAX,begin=-1;

        while(right<ns)
        {
            //进入窗口+维护count
            char in=s[right];
            if(++hash2[in]==hash1[in]) count++;

            while(count==kinds)//判断
            {
                if(right-left+1 <minLen)//更新结果
                {
                    minLen=right-left+1;
                    begin=left;
                }
                //离开窗口+维护count
                char out=s[left++];
                if(hash2[out]==hash1[out]) count--;
                hash2[out]--;
            }
            right++;
        }
        if(begin==-1) return "";
        else return s.substr(begin,minLen);
    }
};

滑动窗口专题结束,接下来是『 二分算法』


=========================================================================

如果你对该系列文章有兴趣的话,欢迎持续关注博主动态,博主会持续输出优质内容

🍎博主很需要大家的支持,你的支持是我创作的不竭动力🍎

🌟~ 点赞收藏+关注 ~🌟

=========================================================================

到了这里,关于【算法】基础算法002之滑动窗口(二)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode算法小抄--滑动窗口算法

    ⚠申明: 未经许可,禁止以任何形式转载,若要引用,请标注链接地址。 全文共计6244字,阅读大概需要3分钟 🌈更多学习内容, 欢迎👏关注👀文末我的个人微信公众号:不懂开发的程序猿 个人网站:https://jerry-jy.co/ 滑动窗口算法 思路 1、我们在字符串 S 中使用双指针中的

    2023年04月09日
    浏览(40)
  • 算法专题二:滑动窗口

    长度最小的子数组 思路一: 思路二: 无重复字符的最长子串 思路一: 最大连续1的个数 开头位0 并且k为0算是一个特殊的情况这样的情况有一些考虑就走不出去前面的0而忽略到后面数组自带1,走不到这些1数据导致记录连续1的个数出问题! 将x减小到0的最小操作数 水果成篮

    2024年02月02日
    浏览(50)
  • 【滑动窗口、矩阵】算法例题

    目录  三、滑动窗口 30. 长度最小的子数组 ② 31. 无重复字符的最长子串 ② 32. 串联所有单词的子串 ③ 33. 最小覆盖子串 ③ 四、矩阵 34. 有效的数独 ② 35. 螺旋矩阵 ② 36. 旋转图像 ② 37. 矩阵置零 ② 38. 生命游戏 ②  给定一个含有  n   个正整数的数组和一个正整数 

    2024年04月14日
    浏览(69)
  • 算法笔记--滑动窗口

    力扣209.长度最小子数组 https://leetcode.cn/problems/minimum-size-subarray-sum/ 在这道题中要注意的不仅仅是滑动窗口的问题,更重要的问题是在循环控制中,不恰当的语法使用会导致这道题出现很严重的问题,这导致我做这道题做了很多天,真的很崩溃。 先来看一下循环的控制问题,

    2024年02月11日
    浏览(45)
  • 【算法小课堂】滑动窗口

    滑动窗口本质是双指针算法的一种演变 本质上就是同向双指针,窗口的范围就是[left,right) 滑动窗口大致可以分为两类 窗口大小不变的 窗口大小变化的 滑动窗口遇到一些验证重复性的问题的时候可以用哈希表来优化 三步走: 窗口的形成初期 进窗口 开始遍历数组,right一直

    2024年02月07日
    浏览(41)
  • 【算法优选】 滑动窗口专题——壹

    基本概念 滑动窗口是一种 基于双指针 的一种思想,两个指针指向的元素之间形成一个窗口。 分类:窗口有两类,一种是 固定大小类 的窗口,一类是 大小动态变化 的窗口。 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长

    2024年02月08日
    浏览(40)
  • 【算法专题】滑动窗口

    题目链接 - Leetcode -209.长度最小的子数组 Leetcode -209.长度最小的子数组 题目:给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl + 1, …, numsr - 1, numsr] ,并返回其长度。 如果不存在符合条件的子数组,返

    2024年02月05日
    浏览(45)
  • 【算法|数组】滑动窗口

    给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度**。**如果不存在符合条件的子数组,返回 0 。 示例 1: 示例 2: 示例 3: 暴力解法 这种做法可以很容易想到,可是谁

    2024年02月12日
    浏览(39)
  • 算法专题整理:滑动窗口

    视频课程:同向双指针 滑动窗口【基础算法精讲 01】_哔哩哔哩_bilibili 滑动窗口也可以理解为双指针法的一种。 滑动窗口的核心在于 连续 !如果需要得到的结果是 满足某种较为明显条件 的 连续 的 子数组 ,可以考虑使用滑动窗口来做。 通常情况下,滑动窗口是 枚举右端

    2024年02月12日
    浏览(47)
  • 算法——滑动窗口

    滑动窗口大致分为两类:一类是窗口长度固定的,即left和right可以一起移动;另一种是窗口的长度变化(例如前五道题),即right疯狂移动,left没怎么动,这类题需要观察单调性(即指针)等各方面因素综合思考 长度最小的子数组 子数组需要为连续的区间 需要在满足条件的前

    2024年04月10日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包