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

coding ability 展开第四幕(滑动指针——巩固篇)超详细!!!!

在这里插入图片描述

文章目录

  • 前言
  • 水果成篮
    • 思路
  • 找到字符串中所有字母异位词
    • 思路
  • 串联所有单词的子串
    • 思路
  • 最小覆盖子串
    • 思路
  • 总结

前言

本专栏上一篇博客,带着大家从认识滑动窗口到慢慢熟悉
相信大家对滑动窗口已经有了大概的认识
其实主要就是抓住——一段连续的区间
今天来学习一些滑动窗口进阶的题目
fellow me

水果成篮

在这里插入图片描述

思路

一开始看到这个题目,一段连续的区间,想到了滑动窗口
然后就想着怎么维护窗口,每次更新到新的水果种类就要,开始对left++,然后处理数据
其实是有点麻烦的,但是经过半个多小时的调试,最后还是ac了
思路:每次更新两个种类的水果,x,y,如果下一个水果的种类不相符合,就更新新的x,y
这个时候 right - 1 和 right 所对应的水果就是新的两种,然后就是处理从 left 到 right - 1这段区间
符合条件的情况, 也就是 从right - 1 一直往前走,到与 right - 1 所对应种类不同的水果,然后再更新结果
在反复进窗口,维护窗口,出窗口

代码如下 :

class Solution
{
public:
    int totalFruit(vector<int>& fruits)
    {
        int ans = 0;
        int n = fruits.size();
        int x = fruits[0], y = fruits[0];
        if (n == 1)
            return 1;
        int left = 0, right = 1;
        for (; right < n; right++)
        {
            if (fruits[right] != x && fruits[right] != y)  // 和前面确定的水果种类
            {
                y = fruits[right - 1];		//  更新新的水果种类  
                x = fruits[right];
                int i = right - 1;
                if (i != left)  // left  到  right - 1  区间  
                {
                    while (fruits[i] == y && i > left)  //  i一直靠近left  直到种类不同
                    {
                        i--;
                    }
                    if (i == left && y != fruits[left])  //  更新  left 的指向
                        left++;
                    else if (i != left)
                        left = i + 1;
                }
            }
            ans = max(ans, right - left + 1);//    更新结果
        }
        return ans;
    }
};

后面又想到了一种思路:
就是用哈希来统计种类数量,哈希相对于前面的那种方法还是简单的
就是把两个种类的水果放入哈希表,然后right++ 水果进窗口,如果哈希表的水果种类大于2
就从左侧 left 开始逐步出窗口,直到哈希表种类等于2,然后更新结果

代码如下:

class Solution
{
public:
    int totalFruit(vector<int>& f)
    {
        unordered_map<int, int> hash; // 统计窗口内出现了多少种水果
        int ret = 0;
        for (int left = 0, right = 0; right < f.size(); right++)
        {
            hash[f[right]]++; // 进窗口
            while (hash.size() > 2) // 判断
            {
                // 出窗口
                hash[f[left]]--;
                if (hash[f[left]] == 0)
                    hash.erase(f[left]);
                left++;
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};

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

在这里插入图片描述

思路

看到又是一段连续的区间,就想到了滑动窗口
这一题 p 的异位词,说白了就是包含了 p 的所有字母,不管先后顺序
想到上一题用哈希优化的爽快,这题好像也可以用哈希来解
把 p 中字符都用哈希统计频次,然后在遍历 s 时,进窗口,维护窗口,出窗口
每次进入窗口,就用哈希统计出现次数,只要没有到达次数上限,就进窗口
如果进入窗口的字符数量大于了 p 的长度,维护窗口从left开始往右开始出窗口
每一次统计进入窗口的数量时,都比较一下 p 的字符个数,如果进入窗口的字符个数等于 p的个数大小相等,就更新结果

代码如下:

class Solution
{
public:
	vector<int> findAnagrams(string s, string p)
	{
		vector<int> ret;
		int hash1[26] = { 0 }; // 统计字符串 p 中每个字符出现的个数
		for(auto ch : p) hash1[ch - 'a']++;
		int hash2[26] = { 0 }; // 统计窗口里面的每一个字符出现的个数
		int m = p.size();
		for(int left = 0, right = 0, count = 0; right < s.size(); right++)
		{
			char in = s[right];
			// 进窗口 + 维护 count
			if(++hash2[in - 'a'] <= hash1[in - 'a']) count++;
			if(right - left + 1 > m) // 判断
			{
				char out = s[left++];
				// 出窗口 + 维护 count
				if(hash2[out - 'a']-- <= hash1[out - 'a']) count--;
			}
			// 更新结果
			if(count == m) ret.push_back(left);
		}
		return ret;
	}
};

下面就上难度了嗷~~~~

串联所有单词的子串

在这里插入图片描述

思路

这个题目看起来很难,其实一点也不简单,看到困难的标签就让人望而生畏
但其实也没有想象的那么难,慢慢抽丝剥茧,其实也能拿下
在这里插入图片描述
看到这里,其实就想到了上一题的那个字母异位词,本题是说所有单词都包含,然后不管顺序
上一题是——所有字母都包含,然后不管顺序,我们不妨试试上一题的思路呢
首先要解决的就是把单词抽象变成字符,我们可以定义一个 string,映射 int 的 哈希表,这个问题就迎刃而解了
下一个问题就是怎么才能知道哪个是单词的开头字母呢??又怎么在 s 中遍历单词然后进窗口呢??
在这里插入图片描述
我又看到了这个条件,雪中送炭,所有单词长度相等,那岂不是起飞了,就让 right 每次遍历 += 单词长度就好了
这些都处理好了,最后一个问题就是,我怎么知道哪个字符是单词的第一个字母,错乱了怎么办,那不是gg
我们只需要在外面套一层for循环,从0到单词的长度,这段区间都做一次滑动窗口就好啦
核心问题都解决了,剩下的就是一些细节处理问题了
话不多说,这些都解决了,开始执行代码:

class Solution 
{
public:
    vector<int> findSubstring(string s, vector<string>& words) 
    {
        vector<int> ret;
        unordered_map<string, int> hash1; // 保存 words 里面所有单词的频次
        for (auto& c : words)
            hash1[c]++;
        int len = words[0].size(), m = words.size();
        for (int i = 0; i < len; i++) // 执行 len 次
        {
            unordered_map<string, int> hash2; // 维护窗口内单词的频次
            for (int left = i, right = i, count = 0; right + len <= s.size();right += len) 
            {
                // 进窗口 + 维护 count
                string in = s.substr(right, len);
                hash2[in]++;
                if (hash1.count(in) && hash2[in] <= hash1[in])
                    count++;
                // 判断
                if (right - left + 1 > len * m) 
                {
                    // 出窗口 + 维护 count
                    string out = s.substr(left, len);
                    if (hash1.count(out) && hash2[out] <= hash1[out])
                        count--;
                    hash2[out]--;
                    left += len;
                }
                // 更新结果
                if (count == m)
                    ret.push_back(left);
            }
        }
        return ret;
    }
};

其实hard题也是由一个一个小问题糅合起来的,解决核心问题,其实也没有那么难
慢慢啃下来,还是有成就感的 come on

最小覆盖子串

在这里插入图片描述

思路

又又又是一段连续的区间,来吧来吧,滑动窗口,滑动窗口
在这里插入图片描述
这道题不是上一题的恰好涵盖所有字符了,要返回的是最小子串,也就是能包含其他的
但是经过前面题目的磨砺,我感觉好像自己有点门道了
思路:用哈希1统计字符串 t 的每一个字符的频次,还有种类
构造一个新的哈希2,然后遍历 s 字符串,每个字符都统计到新的哈希表
当这个字符的频次和 哈希1中统计的字符频次相等时,种类数++
种类数和哈希1种类数相等时维护窗口,更新结果
大致思路就差不多是这样,来执行代码吧

class Solution 
{
public:
    string minWindow(string s, string t) 
    {
        int hash1[128] = {0}; // 统计字符串 t 中每一个字符的频次
        int kinds = 0;        // 统计有效字符有多少种
        for (auto ch : t)
            if (hash1[ch]++ == 0)
                kinds++;
        int hash2[128] = {0}; // 统计窗口内每个字符的频次
        int minlen = INT_MAX, begin = -1;
        for (int left = 0, right = 0, count = 0; right < s.size(); right++) 
        {
            char in = s[right];
            if (++hash2[in] == hash1[in])
                count++;           // 进窗口 + 维护 count
            while (count == kinds) // 判断条件
            {
                if (right - left + 1 < minlen) // 更新结果
                {
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                if (hash2[out]-- == hash1[out])
                    count--; // 出窗口 + 维护 count
            }
        }
        if (begin == -1)
            return "";
        else
            return s.substr(begin, minlen);
    }
};

这个困难也拿下啦,滑动窗口和哈希一起用感觉有点爽,绝佳组合

总结

滑动窗口的核心在于维护一段连续区间,通过哈希表优化统计与比较过程。面对不同问题需灵活调整:
哈希表记录元素频次,快速判断窗口合法性(如水果种类、异位词)
双指针动态伸缩窗口,确保时间复杂度为O(N)
多层循环处理定长元素(如单词串联),覆盖所有起点情况
种类与频次匹配时更新结果,最小子串问题需全局记录最优解
掌握滑动窗口+哈希的组合,能高效解决子串、子数组等连续区间问题,突破Hard瓶颈

今天的内容就到这里啦,不要走开,小编持续更新中~~~~

在这里插入图片描述


http://www.kler.cn/a/589946.html

相关文章:

  • 【华为OD-E卷 - 字符统计及重排 100分(python、java、c++、js、c)】
  • jmeter 循环控制器遍历列表中的数据
  • 20250317笔记本电脑在ubuntu22.04下使用acpi命令查看电池电量
  • test skills
  • 【数据分析】数据筛选与访问行列元素3
  • 2020年蓝桥杯第十一届CC++大学B组(第二次)真题及代码
  • 从被动响应到主动防御——IT 应急演练平台 v3.0.1 重构企业安全免疫系统
  • RPC是啥?
  • 图论part3|101.孤岛的总面积、沉没孤岛、417. 太平洋大西洋水流问题
  • Vue3项目匹配PC端和移动端---一套组件
  • MATLAB语言的编程竞赛
  • 沉浸式vr大空间打造,打造超真实的虚拟体验
  • 【教学类-43-25】20240311 数独3宫格的所有可能(图片版 12套样式,空1格-空8格,每套510张,共6120小图)
  • 配置 VSCode 的 C# 开发环境
  • Matlab 基于专家pid控制的时滞系统
  • Tree of Thought Prompting(思维树提示)
  • 如何在 K8s 内部实现安全的网络隔离?
  • 掌握Python项目的依赖管理:利用`venv`与`conda`高效创建虚拟环境
  • 深度解析ECharts.js:构建现代化数据可视化的利器
  • c++图论(一)之图论的起源和图的概念